Binary Search is a divide-and-conquer paradigm. It searches for an item in a sorted array. In this lesson (tutorial), only sort ascending is considered. The item to search for is called the target value. The target value may or may not be found in the array.

The search begins by comparing the target value with the middle item of the sorted array. If the number of items in the array is even, then the item at half the number is considered the middle item (for example, half of 8 is 4 corresponding to zero based index 3). If the target value is the same as the middle item, then the target value index has been found. If they are not the same, then the target value is either larger or smaller than the middle item. If it is larger, then the lower half of the array will be abandoned, for the search to continue in the upper half. If it is smaller, then the upper half of the array will be abandoned, for the search to continue in the lower half.

The search continues by dividing the half chosen into two again. A comparison between the target value and the middle item of this new half is made. If they are not the same, then this half is divided again into two, and for the same reasons the previous bigger half was divided. If the target value is not the same as the new middle item, then division continues.

When the target value and a middle value (item) are the same, that is conquering. There and then, the search stops. If the target value is not in the array, the search will stop at some final middle item, which is not equal to the target value.

Binary Search Illustration

Consider the sorted list:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16

where the integer, 3, has to be searched. Of course, searching from the beginning, by scanning, will take three operations. That low number of operations is coincidence. However, using binary search, will take four main operations as follows:

The target value is 3. Dividing the list into two, makes 8 the middle item.

Is 8 the same as 3?

No. Since 3 is less than 8, the search will focus on the lower half. That is one main operation done.

Dividing into two again makes 4 the new middle item.

Is 4 the same as 3?

No. Since 3 is less than 4, the search will focus on the new lower half. That is the second main operation done.

Dividing into two again makes 2 the new middle item.

Is 2 the same as 3?

No. Since 3 is greater than 2, the search will then focus on the new upper half. That is the third main operation done.

Dividing into two again makes 3 the new middle item, of a half (sub-list) of length, one. The new and last middle item is now 3.

Is 3 the same as 3?

Yes. The target value has been found. That is the fourth and last main operation done.

When there are 16 items, a maximum of 4 main operations can be made. If there were 16 items, and the target value was in the range and could not be found, 4 main operations would still have taken place.

For example, in the following list:

1, 2, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18

there are still 16 items. A target value of 3 would have ended at the value of 5, with still 4 main operations.

Time Complexity and Binary Search

Worst-Case Performance

Worst-case performance refers to the case where the target value is found at the last main operation, or the target value is in the range of values and is not found at the last main operation.

When the number of items is 16, the maximum number of operations will always be 4.

    16 = 24
    4 = log2(16)

Let n be 16. So,

    4 = log2(n)

If n is 8, the maximum number of operations would be 3 = log2(8). If n is 32, the maximum number of operations would be 5 = log2(32).

The worst-case time complexity (relative speed) for Binary Search is said to be:

    O(log2(n))

where the big O and its parentheses having log2(n) is the notation for time complexity. It is simply written as:

    O(log n)

Best-Case Performance

Assume that the target value was 8 for the first list above. In this case, the first main operation would have found the position of the target value. This is the best-case performance. The time complexity for this best-case performance is written as:

    O(1)

where 1 means one main operation. O(1) is also referred to as constant time.

Coding in JavaScript

The following function is a binary search function. It returns the index of the target found. If target is not found, it returns -1. The reader should read through the code (and comments).

<script type='text/javascript'>
    "use strict";

    function binarySearch(arr, target, n) {
        let loIndex = 0;
        let hiIndex = n - 1;
        let result = -1;    // return -1 when target not found

        while (loIndex <= hiIndex) {
            let midIndex = parseInt((loIndex + hiIndex) / 2);  //integer division
            if (arr[midIndex] <= target) {
                loIndex = midIndex + 1;
                result = midIndex;    //assumed final index, when loIndex == hiIndex
            }
            else
                hiIndex = midIndex - 1;
        }
        return result;
    }
</script>

The output is zero based index 2, as expected, for the above input data. The loIndex means the lowest index of a half (sub-list). The hiIndex means the highest index of a half (sub-list). In the beginning, loIndex is 0 and hiIndex is 15 when n is 16. The while-loop condition ensures that division continues until loIndex is the same as hiIndex (for sub list of one element length), if the target value has not been found yet. That is: the target value may be found at the end of the iteration, when loIndex ==  hiIndex.

A suitable JavaScript calling code segment for the above function is:

<script type='text/javascript'>
    let n = 16;
    let target = 3;
    let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16];
    let indexFound = binarySearch(arr, target, n);

    document.write(indexFound + '<br>');
</script>

Conclusion

Binary search, searches an element in a sorted list. It keeps dividing the list into two sub-lists, checking if the target is in the lower sub-list or the higher sub-list. If the target exists in the range, it would be in a middle element of one sub-list (pair).  The target may not be found because it is within the range, but not one of the listed elements, or it is out of range. In either case, the program should return -1 (however, this aspect was not completely coded in the above code).

The worst-case time complexity for Binary Search is: O(log n)

The best-case time complexity for Binary Search is: O(1)