Sıralanmış bir listede ikili arama nasıl çalışır?

İkili arama, sıralanmış bir listede öğe bulmak için kullanılan ve logaritmik karmaşıklık O(log n) olan bir algoritmadır. "Böl ve yönet" prensibiyle çalışır:

1. Listenin ortadaki öğesi belirlenir.
2. Aranan öğe ortadakiyle eşitse, arama sona erer.
3. Aranan öğe ortadan küçükse, arama listenin sol yarısında devam eder.
4. Daha büyükse, sağ yarısında devam eder.

İşlem, öğe bulunana kadar veya arama aralığı tükenene kadar yinelemeli veya özyinelemeli olarak devam eder.

Go dilinde örnek:

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // öğe bulunamadı
}