Welke methoden kunnen worden gebruikt om snel een element te zoeken in een gesorteerde array, terwijl de tijd wordt geminimaliseerd?

Om snel een element te vinden in een gesorteerde array, wordt meestal het binaire zoekalgoritme gebruikt. Het minimaliseert de tijd, omdat het in O(log n) werkt, waarbij n de grootte van de array is.

Idee van binaire zoekopdracht:

• Vergelijk het gezochte element met het element in het midden van de array.
• Als ze gelijk zijn, is het element gevonden.
• Als het gezochte element kleiner is, zoek dan in de linkerhelft.
• Als het groter is, in de rechterhelft.

Op iOS (Swift) kun je de methode binarySearch gebruiken of deze zelf implementeren.

Voorbeeld in Swift:

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

let sortedArray = [1, 3, 5, 7, 9]
if let index = binarySearch(sortedArray, target: 5) {
    print("Element gevonden op positie \(index)")
} else {
    print("Element niet gevonden")
}