Binary Search

October 22, 2022

algorithmswiftjava

O(log n)

Preconditions

• The array must be sorted

Swift

func binarySearch(numbers: [Int], target: Int) -> Int {
    var index = 0
    var r = numbers.count

    while index < r {
        let middle = (index + r) / 2
        if numbers[middle] < target {
            index = middle + 1
        } else {
            r = middle
        }
    }
    return index
}

Java

static int binarySearch(int[] numbers, int target) {
    int index = 0, r = numbers.length;
    while (index < r) {
        int middle = (index + r) / 2;
        if (numbers[middle] < target)
            index = middle + 1;
        else
            r = middle;
    }
    return index;
}