How does binary search work in a sorted list?

Binary search is an algorithm for finding an element in a sorted list with logarithmic complexity O(log n). It works on the principle of "divide and conquer":

1. The middle element of the list is determined.
2. If the sought element equals the middle, the search ends.
3. If the sought element is less than the middle, the search continues in the left half of the list.
4. If greater — in the right half.

The process repeats recursively or iteratively until the element is found or the search range is exhausted.

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
}