Milyen módszerek használhatók egy rendezett tömbben lévő elem gyors keresésére, minimalizálva az időt?

Gyors elem kereséshez egy rendezett tömbben általában a bináris keresést alkalmazzuk. Ez minimalizálja az időt, mivel O(log n) idő alatt működik, ahol n a tömb mérete.

A bináris keresés ötlete:

• Hasonlítsuk össze a keresett elemet a tömb közepén lévő elemmel.
• Ha egyeznek, megtaláltuk az elemet.
• Ha a keresett elem kisebb, keressük a bal felében.
• Ha nagyobb, a jobb felében.

iOS (Swift) esetén használhatja a binarySearch metódust vagy saját maga is megvalósíthatja.

Swift példakód:

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("Elem megtalálva a pozíción \(index)")
} else {
    print("Elem nem található")
}