Тартиптелген массивде элементти тез табуу үчүн кайсы ыкмаларды колдонсо болот жана убакытты кантип минималдаштырса болот?

Тизмектеги элементти тез табуу үчүн адатта бинардык издөө алгоритми колдонулат. Ал убакытты минималдаштырат, анткени ал O(log n) убакытта иштейт, анда n — массивдин өлчөмү.

Бинардык издөө идеясы:

• Изделүүчү элементти массивдин ортосундагы элемент менен салыштыруу.
• Эгер тең болсо, элемент табылды.
• Эгер издөөчү элемент кичик болсо, сол жарымда издөө жүргүзүңүз.
• Эгер чоң болсо, оң жарымда.

iOS (Swift) колдонуп, binarySearch ыкмасын колдонсоңуз болот же өзүңүз ишке ашыра аласыз.

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("Элемент табылды позицияда \(index)")
} else {
    print("Элемент табылбады")
}