Kādus metodes var izmantot, lai ātri atrastu elementu sakārtotā masīvā, minimizējot laiku?

Lai ātri atrastu elementu sakārtotā masīvā, parasti izmanto bināro meklēšanu. Tas samazina laiku, jo darbojas O(log n) laikā, kur n ir masīva lielums.

Binārās meklēšanas ideja:

• Salīdzināt meklējamo elementu ar elementu masīva vidū.
• Ja tie ir vienādi, elements ir atrasts.
• Ja meklējamais elements ir mazāks, turpini meklēt kreisajā pusē.
• Ja lielāks, labajā pusē.

iOS (Swift) var izmantot binarySearch metodi vai to pats realizēt.

Piemērs 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("Elements at position \(index) found")
} else {
    print("Element not found")
}