Ricerca sequenziale

Niente fonti!
Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.
Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.
Ricerca sequenziale
ClasseAlgoritmo di ricerca
Struttura datiArray
Caso peggiore temporalmente
Caso ottimo temporalmente
Caso medio temporalmente
OttimaleSì
Manuale

In informatica la ricerca sequenziale (o ricerca lineare) è un algoritmo utilizzabile per trovare un elemento in un insieme non ordinato.

L'algoritmo controlla in sequenza gli elementi dell'insieme, arrestandosi quando ne trova uno che soddisfa il criterio di ricerca; non potendosi avvalere di alcun ordinamento tra gli elementi, l'algoritmo può concludere con certezza che l'insieme non contiene alcun elemento corrispondente solo dopo averli verificati tutti, richiedendo pertanto un numero di controlli, nel caso peggiore, pari alla cardinalità dell'intero insieme.

Implementazioni

Linguaggio C

Ecco un'implementazione in C di detto algoritmo. Il parametro insieme è un array in cui cercare, x è l'elemento da cercare e infine n è il numero di elementi contenuti nell'array. 

int ricercaSequenziale(int insieme[], int x, int n) {
     int i;
     for (i = 0; i < n; ++i) {
       // Interrompe la ricerca con successo alla prima corrispondenza trovata
       if (insieme[i] == x) return i;
     }
     // L'intera sequenza è stata esaurita senza trovare corrispondenze
     return -1;
 }

Java

Ecco l'algoritmo della ricerca sequenziale per elementi interi implementato in linguaggio Java: 

/* 
 *  Ricerca sequenziale, scandisce tutto l'array di interi per trovare la "chiave"(key) cercata
 *
 *  @param array l'array di elementi interi
 *  @param key l'elemento intero da cercare
 *  @return la posizione dell'elemento cercato
*/
 public int ricercaSequenziale(int [] array , int key) {
     for (int i=0; i<array.length; i++)
          if (array[i]==key);
              return i;
     return -1; //restituisce -1 se non trova l'elemento da cercare
 }

Python

Ecco una variante in linguaggio Python. Funziona con qualunque tipo di iterabile, incluse liste e stringhe. 

def RicercaSequenziale(lista,chiave):
    for i in range(len(lista)):
        if lista[i] == chiave:
            return i
    return False

Variante con sentinella

L'algoritmo classico richiede che, dopo ciascun elemento non corrispondente, si verifichi se ci si trova al termine della sequenza per decidere se terminare (con esito negativo) o proseguire con l'elemento successivo. Tale verifica può essere evitata se l'algoritmo ha la possibilità di modificare l'insieme su cui avviene la ricerca: aggiungendo un ulteriore elemento, pari a quello cercato, al termine della sequenza, l'algoritmo ha la certezza di trovare almeno una corrispondenza. La ricerca avrà, nel suo complesso, esito positivo se la corrispondenza è stata trovata in una posizione precedente all'ultima.

Questa variante, pur introducendo una semplificazione del passo iterativo, non altera l'ordine di complessità dell'algoritmo nel suo complesso, che rimane lineare.

Implementazione in linguaggio C

Eccone un'implementazione in linguaggio C: 

 // Si assume che "lista" abbia capacità di almeno n-1 elementi, ovvero
 // che lista[n] sia una valida locazione di memoria.
 int ricercaSequenzialeConSentinella(int lista[], int x, int n) {
     // Aggiunta della sentinella
     lista[n]=x;

     // Scansione sino alla prima corrispondenza
     int i = 0;
     while (lista[i] != x) i++;

     // Identificazione dell'esito
     return (i > n) ? i : -1;
 }

Collegamenti esterni

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica

Read other articles:

Diskografi Iz*One

Diskografi Iz*OneAlbum studio2Extended play4Singel9Singel promosional2Kolaborasi1 Discography dari girl grup Korea Selatan–Jepang Iz*One terdiri dari dua studio album, empat extended play, dan tujuh singel. Pada Mei 2021, Iz*One telah menjual lebih dari 2,79 juta album gabungan. Rilisan debut duodecet, EP Color Iz, dirilis pada 29 Oktober 2018. Rilisan Korea diikuti dengan single debut Jepang grup, Suki to Iwasetai, dirilis pada 6 Februari 2019 di bawah label UMG milik EMI Records. Ini kemu...

 

Gwion Gwion rock paintings

Rock art in Western Australia Gwion Gwion (Tassel) figures wearing ornate costumes The Gwion Gwion rock paintings, Gwion figures, Kiro Kiro or Kujon (also known as the Bradshaw rock paintings, Bradshaw rock art, Bradshaw figures and the Bradshaws) are one of the two major regional traditions of rock art found in the north-west Kimberley region of Western Australia.[1][2] Key traditional owners have published their own account of the meaning of the images.[3] However th...

 

Tŷ Pont Haearn

Residential building in Cardiff, Wales Tŷ Pont HaearnTŷ Pont HaearnGeneral informationTypeResidentialLocationCardiff, WalesAddressPellett Street, Cardiff city centreCoordinates51°28′40″N 3°10′13″W / 51.4778°N 3.1702°W / 51.4778; -3.1702Current tenantsUnite StudentsNCPConstruction startedMarch 2004CompletedSeptember 2005Cost£19.7 millionOwnerUNITE GroupHeight63 metresTechnical detailsFloor count21Design and constructionArchitect(s)Wigley Fox Partners...

Barat Academy

This article has multiple issues. Please help improve it or discuss these issues on the talk page. (Learn how and when to remove these template messages) This article may need to be rewritten to comply with Wikipedia's quality standards. You can help. The talk page may contain suggestions. (October 2022) This article contains wording that promotes the subject in a subjective manner without imparting real information. Please remove or replace such wording and instead of making proclamations ab...

 

Patroklos

Akhilles membalut luka Patroklos, hiasan pada piala kuno. Dalam mitologi Yunani, Patroklos (Yunani: Πάτροκλος) adalah pahlawan putra Menoitios dan cucu Aktor. Dia adalah kekasih pria atau sahabat Akhilles. Kisahnya diceritakan dalam Iliad karya Homeros. Silsilah Menoitios adalah salah seorang Argonaut ketika muda. Dia menikah beberapa kali, karena itu ada empat perempuan yang disebut-sebut sebagai ibu Patroklos. Apollodoros dari Athena menyebut tiga nama: Periopis (putri Feres, p...

 

趙家驤

追晉陸軍二級上將趙家驤將軍个人资料出生1910年 大清河南省衛輝府汲縣逝世1958年8月23日(1958歲—08—23)（47—48歲） † 中華民國福建省金門縣国籍 中華民國政党 中國國民黨获奖 青天白日勳章（追贈）军事背景效忠 中華民國服役 國民革命軍 中華民國陸軍服役时间1924年－1958年军衔 二級上將 （追晉）部队四十七師指挥東北剿匪總司令部參謀長陸軍�...

Cagliari Calcio 2009-2010

Voce principale: Cagliari Calcio. Cagliari CalcioStagione 2009-2010Sport calcio Squadra Cagliari Allenatore Massimiliano Allegri[1] Giorgio Melis All. in seconda Marco Landucci[1] Gianluca Festa Presidente Massimo Cellino Serie A16º posto. Coppa ItaliaTerzo turno. Maggiori presenzeCampionato: Agostini (38) Miglior marcatoreCampionato: Matri (13)Totale: Matri (13) StadioStadio Sant'Elia 2008-2009 2010-2011 Si invita a seguire il modello di voce Questa voce raccoglie le i...

 

The Land (newspaper)

English language newspaper published by Australian Community Media The LandTypeWeekly newspaperOwner(s)Australian Community MediaFounder(s)NSW Farmers and Settlers AssociationEditorAndrew NorrisLanguageEnglishHeadquartersNorth Richmond, N.S.W.ISSN0023-7523Websitehttp://www.theland.com.au/ The Land is an English language newspaper published in Sydney and later in North Richmond, New South Wales by Australian Community Media. The newspaper commenced publication in 1911. History The front page o...

 

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

Edward Blore

Edward Blore Edward Blore (Derby, 13 settembre 1787 – Derby, 4 settembre 1879) è stato un architetto e antiquario inglese. Indice 1 Biografia 2 Opere 3 Note 4 Bibliografia 5 Voci correlate 6 Altri progetti 7 Collegamenti esterni Biografia Buckingham Palace completato da Blore nel 1850. In seguito è stato rettificato e modificato da Sir Aston Webb nel 1913 Palazzo Vorontsov ad Alupka Government House di Sydney Edward Blore, architetto e antiquario, nacque a Derby il 13 settembre 1789, figl...

 

Arjun Rampal

Indian film actor, model, producer (born 1972) Arjun RampalRampal at an event in 2012Born (1972-11-26) 26 November 1972 (age 51)Jabalpur, Madhya Pradesh, IndiaAlma materHindu College, DelhiOccupationsActormodelfilm producertelevision personalityYears active1994–presentSpouse Mehr Jesia ​ ​(m. 1998; div. 2019)​PartnerGabriella Demetriades (2019–)Children4 Arjun Rampal (born 26 November 1972) is an Indian actor, model, film prod...

 

Fungsi aljabar

Dalam matematika, fungsi aljabar adalah fungsi yang bisa didefinisikan sebagai akar dari sebuah persamaan aljabar. Fungsi aljabar merupakan ekspresi aljabar menggunakan sejumlah suku terbatas, yang melibatkan operasi aljabar seperti penambahan, pengurangan, perkalian, pembagian, dan peningkatan menjadi pangkat pecahan. Contoh dari fungsi tersebut adalah: f ( x ) = 1 / x {\displaystyle f(x)=1/x} f ( x ) = x {\displaystyle f(x)={\sqrt {x}}} f ( x ) = 1 + x 3 x 3 / 7 − 7 x 1 / 3 {\display...

Abdul Wahid Aresar

Scholar, writer, researcher and politician of Pakistan Abdul Wahid Arisarعبدالواحد آريسرBornAbdul Wahid Arisar(1949-10-11)11 October 1949Village Waoori, District: UmarkotDied3 May 2015(2015-05-03) (aged 65)Karachi, SindhResting placeBuried at Village Unar Abad, District: UmarkotOther namesArisar, Molvi Abdul Wahid ArisarEducationMolvi ArabicAlma materPrimary School Sabho, Bhendo Shareef, Madarsa Hashmia Sujawal, Madarsa Muftah-ul-Uloom Hyderabad, Shah Waliullah Ac...

 

حرف سياد

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (سبتمبر 2020) حرف سياد تقسيم إداري  البلد لبنان  التقسيم الأعلى قضاء الضنية  تعديل مصدري - تعديل   حرف سياد هي ...

 

Hubert H. Humphrey Metrodome

Hubert H. Humphrey MetrodomeMetrodome, Mall of America Field, The Homerdome, The Dome, The Thunderdome Informasi stadionPemilikMetropolitan Sports Facilities CommissionOperatorMetropolitan Sports Facilities CommissionLokasiLokasi900 South 5th StreetMinneapolis, Minnesota 55415Koordinat44°58′26″N 93°15′29″W / 44.97389°N 93.25806°W / 44.97389; -93.25806KonstruksiMulai pembangunan20 Desember 1979DibukaApril 1982Biaya pembuatan$55 juta[1]($190 juta...

奴隸貿易

此條目没有列出任何参考或来源。 (2009年3月26日)維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。 奴隶制度 现代奴隶制度 非洲 孟加拉国 欧洲 海地 印度 马里 毛里塔尼亚 朝鲜 巴基斯坦 苏丹 美国 类型 童养媳 童工 债役 人口贩卖 雇农 刑役 性奴隶 血汗工厂 雇佣奴隶 历史 中国（西藏） 古代地中海�...

 

With Love, Chér

1967 studio album by CherWith Love, ChérStudio album by CherReleasedOctober 23, 1967Recorded1966–67GenrePopfolkLength31:05LabelLibertyImperialBGO RecordsProducerSonny BonoCher chronology Chér(1966) With Love, Chér(1967) Backstage(1968) Singles from With Love, Chér Behind the DoorReleased: October 24, 1966 Mama (When My Dollies Have Babies)Released: November 28, 1966 Hey JoeReleased: July 31, 1967 You Better Sit Down KidsReleased: October 2, 1967 Professional ratingsReview scores...

 

Miriam Goldman Cedarbaum

American judge (1929–2016) Miriam Goldman CedarbaumSenior Judge of the United States District Court for the Southern District of New YorkIn officeMarch 31, 1998 – February 5, 2016Judge of the United States District Court for the Southern District of New YorkIn officeMarch 4, 1986 – March 31, 1998Appointed byRonald ReaganPreceded byCharles E. Stewart Jr.Succeeded byNaomi Reice Buchwald Personal detailsBornMiriam R. Goldman[1](1929-09-16)September 16, 1929Crown H...

إيزابيل دو لودر

تحتاج هذه المقالة كاملةً أو أجزاءً منها لإعادة الكتابة حسبَ أسلوب ويكيبيديا. فضلًا، ساهم بإعادة كتابتها لتتوافق معه. إيزابيل دو لودر العشيقة الرسميةماركيزة لودر (بالفرنسية: Isabelle de Ludres)‏  لوحة لودر تجسد مريم المجدلية في 1677. معلومات شخصية الميلاد سنة 1647   لودر، دوقية لو�...

 

بلدة ديكاتور (ميشيغان)

بلدة ديكاتور الإحداثيات 42°06′46″N 85°57′29″W / 42.112777777778°N 85.958055555556°W / 42.112777777778; -85.958055555556   [1] تقسيم إداري  البلد الولايات المتحدة  التقسيم الأعلى مقاطعة فان بورين  خصائص جغرافية  المساحة 35.5 ميل مربع  ارتفاع 239 متر  عدد السكان  عدد السكان 3575 (1 ...