Den binära sökalgoritmen är ett mer effektivt sätt att söka efter ett specifikt element i en sorterad lista. Till skillnad från linjär sökning, som kontrollerar element sekventiellt, delar binär sökning listan i halvor och jämför målelementet med mittelementet. Denna process upprepas tills målelementet hittas eller sökintervallet blir tomt.
Hur det fungerar
- Börja med hela den sorterade listan.
- Hitta mittelementet i det aktuella sökintervallet.
- Jämför mittelementet med målvärdet.
- Om mittelementet är lika med målvärdet är sökningen framgångsrik.
- Om mittelementet är större än målet, sök i den vänstra halvan av intervallet.
- Om mittelementet är mindre än målet, sök i den högra halvan av intervallet.
- Upprepa steg 2-6 tills målelementet hittas eller sökintervallet blir tomt.
Exempel
Låt oss överväga en sorterad lista med heltal och vill hitta talet 34 med binär sökning.
Sorterad lista: {12, 23, 34, 45, 56, 67, 89, 90}
- Börja med hela listan.
- Mellanelement: 56(position 4). Jämför med 34.
- 56 är större än 34. Sök i den vänstra halvan.
- Nytt mittelement: 23(position 1). Jämför med 34.
- 23 är mindre än 34. Sök i den högra halvan.
- Nytt mittelement: 45(position 3). Jämför med 34.
- 45 är större än 34. Sök i den vänstra halvan.
- Nytt mittelement: 34(position 2). Mål hittat.
Exempelkod i C++
I det givna exemplet binarySearch
används funktionen för att hitta talet 34 i en sorterad lista med heltal. Resultatet blir positionen 34 i listan(positionerna börjar från 0) eller -1 om numret inte hittas.