How long does binary search work for?

Binary search operates in O(log n) time, where n is the number of elements in the sorted array. This is achieved because at each step, the algorithm halves the search space, discarding half of the elements that cannot contain the target value.

Example in Go:

func binarySearch(arr []int, target int) int {
    left, right := 0, len(arr)-1
    for left <= right {
        mid := left + (right-left)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return -1 // element not found
}