Binary Search

Task: Find 23 in this sorted array

public static int binarySearch(int[] arr, int target) {    int low = 0, high = arr.length - 1;     while (low <= high) {        int mid = low + (high - low) / 2;         if (arr[mid] == target) {            return mid; // found        } else if (arr[mid] < target) {            low = mid + 1; // search right half        } else {            high = mid - 1; // search left half        }    }    return -1; // not found}

What you are watching

Binary search over the sorted array 4, 11, 17, 23, 31, 42, 56, 68, 79, looking for 23. Each step checks the middle value of the range still in play and discards the half that cannot contain the target. The range shrinks from 9 values to 9, then 4, then 2, then 1, and 23 is found at index 3 after 4 comparisons. Because every step halves what is left, the work grows with the logarithm of the input rather than with the input itself.