algorithmBinary Search

O(log n)

Preconditions

• Array should be sorted

Swift

func binarySearch(numbers: [Int], target: Int) -> Int {
    var left = 0
    var right = numbers.count
    
    while left < right {
        let middle = (left + right) / 2
        if numbers[middle] < target {
            left = middle + 1
        } else {
            right = middle
        }
    }
    return left
}

Kotlin

fun binarySearch(numbers: Array<Int>, target: Int): Int {
    var left = 0
    var right = numbers.size

    while (left < right) {
        val middle = (left + right) / 2
        if (numbers[middle] < target) {
            left = middle + 1
        } else {
            right = middle
        }
    }
    return left
}

Java

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