When you are dealing with an array that is in sorted order, there are new doors that open to find an element within the array. For example, finding the smallest item in a sorted array is just looking at the first element, and the same is true with finding the largest element as well! Not only that, there is another trick that makes finding any element in the array much faster than linear search, called Binary Search.

Assumptions

What is Binary Search?

Binary Search, known also as logarithmic search, is a decrease and conquer searching algorithm that finds elements in a sorted array by jumping to the midpoint of the array, comparing the midpoint to the item being searched for, and discarding the half of the array that is greater than or less than the item. This continues until a single element is left and the item has been found.

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_BinarySearch_01.png" alt="binary-search diagram" style="max-width:95%;">

</div>

Conceptualization

Let's say we have a sorted array arr = { 1, 2, 4, 5, 8, 9, 12, 14, 17, 18, 20 } and are looking to find if the array contains 5. With linear search, we would have to check each element individually. Instead, we'll use binary search to find the element faster.

The length of arr is 11. Dividing by 2 (and rounding down) will tell us that the midpoint of this starting array is arr[5] == 9 .

5 &lt; 9, so we discard the top half of the array and look for the midpoint of the sub array arr[0] to arr[5].

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_BinarySearch_02.png" alt="first binary search iteration" style="max-width:95%;">

</div>

The length of our sub-array is now 5. When divided by 2, and rounded down, the new midpoint is now arr[2] == 4. This time 5 &gt; 4, which means that we need to find the next midpoint between arr[2] and arr[5].

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_BinarySearch_03.png" alt="second binary-search iteration" style="max-width:95%;">

</div>

The length of the current sub array is now 3. 3 / 2 = 1.5, which rounds down to 1. Because we are starting at arr[2], we add an offset of 1, making our new midpoint arr[3].

arr[3] == 5: we have successfully found the value using binary search!

<div style="width:100%; margin:auto;text-align:center;"> <img src="https://www.devmaking.com/img/topics/algs/Algs_BinarySearch_04.png" alt="final binary-search iteration" style="max-width:95%;">

</div>

To model what just happened in code:

 function binarySearch( int [] arr, int value ) {
   // The left and right edges of the array
   // these help define the sub array.
   int left = 0;
   int right = arr.length - 1;

   // ( While the array is greater than 1 in size. )
   while ( left &lt;= right ){
     // Find the midpoint of the sub array.
     midpoint = floor( (left + right ) / 2 );
     // If the value is greater than the midpoint..
     if ( arr[midpoint] &lt; value ) {
       // .. Remove the left half of the array.
       left = midpoint + 1;
     }
     // Or, if the value is less than the midpoint..
     else if ( arr[midpoint] &gt; value ) {
       // .. Remove the right half of the array.
       right = midpoint - 1;
     }
     // Otherwise, we've found the value!
     else {
       return midpoint;
     }
   }
   // The value doesn't exist in the array!
   return -1;
 }

Binary search works by splitting an array into two pieces, only using one half for the next split. Utilizing only one of the two sub arrays is what makes this a decrease and conquer algorithm and not a divide and conquer algorithm, although both share in being able to utilize the recurrence relation solver.

Recalling <a href="https://www.devmaking.com/learn/algorithms/master-theorem/" target="_blank" style="color:inherit;">The Master Theorem</a>:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">T(n) = aT( n/b ) + O(n<sup>d</sup>)</div> Taking this step by step:

  • We jump to the midpoint of the remaining array each iteration; b = 2.
  • Then, we discard the half of the array that does not contain the value; a = 1.
  • Once the value is found, it is returned and no more work is done. O(1), d = 0.

This results in T(n) = (1)T(n/2) + O(1).

Plugging this into the equation results in 0 = log<sub>2</sub>1.

Using the corresponding formula yields:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">n<sup>d</sup>log<sub>b</sub>n = n<sup>0</sup>log<sub>2</sub>n</sup></div> Which evaluates to a final result of:

<div style="width:100%;text-align:center;font-style:italic;font-size:150%;">O(log n)&#8718;</div> <br>

Best Worst Average Memory
O(1) O(log n) O(log n) O(1)

<br>

> Binary Search is an optimal searching algorithm with a worst case runtime of O(log n).

  • When you are working with a sorted array
  • If the array is not sorted, it may be worth sorting the array if possible, especially if the array will need to be searched multiple times.

Further Resources