Kokias metodas galima naudoti greitai ieškant elemento surūšiuotame masyve, sumažinant laiką?

Greitai surasti elementą surūšiuotame masyve dažniausiai naudojamas binarinis paieškos algoritmas. Jis sumažina laiką, nes veikia O(log n) laiku, kur n yra masyvo dydis.

Binarinės paieškos idėja:

• Palyginti ieškomą elementą su elemento viduryje masyvo.
• Jei jie lygūs, elementas rastas.
• Jei ieškomas elementas mažesnis, tęsti paiešką kairėje pusėje.
• Jei didesnis, dešinėje pusėje.

iOS (Swift) galite naudoti binarySearch metodą arba įgyvendinti patys.

Pavyzdys 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("Elementas rastas pozicijoje \(index)")
} else {
    print("Elementas nerastas")
}