Binärsökning

Snabböversikt

Binärsökning hittar ett värde i en sorterad array genom att jämföra med mitten. Varje jämförelse kan halvera antalet kandidater, vilket ger O(log n) tid.

Prova själv

INTERACTIVE / LIVE

Binärsökning

Välj ett värde och följ sökintervallet.

Live demo

Så fungerar sökningen

Ange gränser. Börja med index 0 och sista giltiga index.
Beräkna mitten. Jämför målet med värdet i mitten.
Välj rätt halva. Om mitten är för liten, flytta vänstergränsen. Om den är för stor, flytta högergränsen.
Upprepa. Sluta när värdet hittas eller intervallet är tomt.

static int BinarySearch(int[] sorted, int target)
{
    int left = 0, right = sorted.Length - 1;
    while (left <= right)
    {
        int middle = left + (right - left) / 2;
        if (sorted[middle] == target) return middle;
        if (sorted[middle] < target) left = middle + 1;
        else right = middle - 1;
    }
    return -1;
}

#include <vector>
int binarySearch(const std::vector<int>& sorted, int target) {
    int left = 0, right = static_cast<int>(sorted.size()) - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (sorted[mid] == target) return mid;
        if (sorted[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

Kostnad och testfall

Tidsåtgången är O(log n) och den iterativa metoden använder O(1) extra minne. Testa en tom array, ett enda värde, ett värde som saknas och träffar i början och slutet.

Varför sökområdet krymper

Binärsökning håller reda på ett intervall där målet fortfarande kan finnas. Om mittenvärdet är för litet kan allt till och med mitten tas bort. Om värdet är för stort kan den övre delen tas bort. På så sätt bevaras möjligheten att hitta målet samtidigt som sökområdet minskar.

Vanliga indexfel

Bestäm om den högra gränsen är inkluderad. En inkluderande variant börjar med right = length - 1 och kör medan left <= right. Ett halvöppet intervall börjar med right = length och använder left < right. Båda fungerar, men du får inte blanda reglerna.

Testa gränsfallen

Kontrollera tomma arrayer, enstaka värden, första och sista positionen samt mål som saknas. Om värdet förekommer flera gånger kanske den vanliga algoritmen hittar vilken träff som helst. Behöver du första förekomsten måste det stå i kraven och koden.

Läs vidare

Relaterad lektionTidskomplexitetLär dig analysera hur många steg algoritmen behöver.

Kontrollfråga

TESTA KUNSKAPEN

Vad måste vara sant för att binärsökning ska fungera korrekt?

Visa förklaring

Genom att sortera kan vi avgöra vilken halva som är säker att kasta bort.