Welche Methoden können verwendet werden, um ein Element in einem sortierten Array schnell zu suchen und die Zeit zu minimieren?

Um schnell ein Element in einem sortierten Array zu finden, verwendet man in der Regel den binären Suchalgorithmus. Dieser minimiert die Zeitkosten, da er in O(log n) läuft, wobei n die Größe des Arrays ist.

Idee der binären Suche:

• Vergleichen Sie das gesuchte Element mit dem Element in der Mitte des Arrays.
• Wenn sie gleich sind, ist das Element gefunden.
• Wenn das gesuchte Element kleiner ist, suchen Sie in der linken Hälfte.
• Wenn es größer ist, in der rechten Hälfte.

Auf iOS (Swift) können Sie die Methode binarySearch verwenden oder sie selbst implementieren.

Beispiel 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 gefunden an Position \(index)")
} else {
    print("Element nicht gefunden")
}