What is the complexity of the binary search algorithm?

The complexity of binary search algorithm is O(log n), where n is the number of elements in the sorted array.

Explanation: at each step, binary search divides the search area in half, discarding half of the elements. Thus, the number of operations grows logarithmically with the size of the input data.

Example in Java:

int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int 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
}