Selgitage binaarse otsingu algoritmi tööpõhimõtet ja selle omadusi.

Binaarotsingu algoritm on kasutatav järjestatud massiivi või nimekirja elemendi leidmiseks. Selle põhimõte:

1. Määratakse massiivi keskne element.
2. Kui otsitav element on võrdne keskmega, lõpeb otsing.
3. Kui otsitav element on väiksem kui keskne, jätkatakse otsingut vasakul poolel.
4. Kui suurem, paremal poolel.
5. Protsess kordub rekursiivselt või iteratiivselt, kuni element leitakse või otsinguulatus ammendub.

Omadused:

• Töötleb ainult järjestatud andmetega.
• Keerukus — O(log n), palju kiirem kui lineaarne otsing.
• Vajab juurdepääsu elementidele indeksi kaudu (nt. massiiv).

Näide Swiftis:

func binarySearch(_ array: [Int], _ target: Int) -> Int? {
    var left = 0
    var right = array.count - 1
    
    while left <= right {
        let mid = (left + right) / 2
        if array[mid] == target {
            return mid
        } else if array[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return nil
}

let numbers = [1, 3, 5, 7, 9]
if let index = binarySearch(numbers, 7) {
    print("Element found at position \(index)")
} else {
    print("Element not found")
}