a pod indeksem nie ma poszukiwanej wartości.
Implementacja Zastosowano język TypeScript.
/** * Zwraca indeks poszukiwanego elementu * lub null jeśli dany element w tablicy nie istnieje. * * @param tablica - posortowana tablica liczb. * @param szukana - poszukiwana wartość. */ function wyszukiwanieBinarnie(tablica: number[], szukana: number): number { let lewo = 0; let prawo = tablica.length - 1; let przeszukiwany_indeks;
while (lewo <= prawo) { przeszukiwany_indeks = Math.floor((lewo + prawo) / 2); if (tablica[przeszukiwany_indeks] < szukana) { lewo = przeszukiwany_indeks + 1; } else if (tablica[przeszukiwany_indeks] > szukana) { prawo = przeszukiwany_indeks - 1; } else { return przeszukiwany_indeks;
return null; }
Wyszukiwanie interpolacyjne Wariant wyszukiwania binarnego, w którym punkt podziału (indeks ) jest wyznaczany metodą interpolacji liniowej.
Jeśli wartości kluczy na krańcach przedziału wynoszą i i poszukiwana wartość wówczas indeks można wyznaczyć jako gdzie parametr wynika z wartości kluczy: