Binary search algorithm in Java

Last updated : Jul 30, 2023 12:00 AM

1. What is Binary Search?

Binary search is used to find a target value in an array. The goal is to find the target value with a minimum number of attempts or iterations. The binary search algorithm operates on sorted arrays. Search iterations are performed on the array by repeatedly dividing the search interval in half. If the search value is less than the value in the middle of the search interval, discard the upper half and continue with the lower half. Iterate this process until the search value is found or no interval is left.

2. How to implement binary search

Let's take the below array and implement the binary search algorithm to find a given value. To make it practical, let's begin with an unsorted array.

unsorted array

int array[] = {30,1,40,50,31,2,8,3,6,5};

The first step is to sort the array to make it binary sort ready. This is crucial since we use the indexes of the array elements during the sorting process to compare the actual value contained in the index. The below code uses java to sort the array, but the logic is applicable for any programming language.

unsort array

Arrays.sort(array);

The sorted array will look like {1,2,3,5,6,8,30,31,40,50}

Now, this array is ready to be binary searched. Let's pick a random number to search: 40. At the end of this tutorial, we will do the full code implementation of binary search. With our implementation, a search for random value 40 would look like this.

Binary search 40

binarySearch(array,40);

2.1 Find the index of the middle position

Our sorted array length is 10. Since we use the index of the position, the first index becomes 0, and the last index is array length -1. Using these numbers, we can calculate the middle position as:

start = 0
end = array.length-1 = 9
middle = ((start + end) / 2) = int 9 / int 2 = 4

This leads us to position 4 in the array. Position 4 holds the value 6, which is smaller than the value we are looking for. Now we know 40 lies between index 5 and 9. Therefore, we can discard the portion of the array lower than index 5 (lower half) and continue our search with the upper half where the index is 5 or greater.

Figure 1 : First iteration in search for value 40

2.2 Eliminate and continue

Now our focus is between index 5 and 9. Let's eliminate the remaining portion of the array. Our start position becomes middle + 1 and the end position remains the end of the array.

Since 40 > 6 at array[middle]
start = middle + 1 = 5
middle = (5 + 9) / 2 = 7

Index 7 is our new middle. This position holds 31, which is still smaller than our search value of 40.

Figure 2 : Second iteration in search for value 40

Now we can eliminate the array index lower than 8. Our search value lies on or above index position 8.

Since 40 > 31 at array[middle]
start = middle + 1 = 8
middle = (8 + 9) / 2 = 8

Now our middle is 8 and we find what we are looking for. At this point, it is not necessary to continue with the search, we can simply return the position and exit the function.

Figure 3 : Third iteration in search for value 40

The source code for this example is listed below.

3. Implementing Binary Search

3.1 Binary Search using while loop

This is the preferred implementation for larger arrays.

Using while loop

private static int binarySearch(int[] array, int val)
{
   Arrays.sort(array);
   int start = 0;
   int end = array.length-1;
   int middle;
   while(start <= end)
   {
      middle = (start + end) / 2;
      if(array[middle] == val){
         return middle;
      }
      if(array[middle] < val){
         start = middle +1;
      }
      else{
         end = middle -1;
      }
   }
   return -1;
}

3.2 Binary Search using Recursion

Recursion consumes more resources. Every recursive iteration has to maintain its stack. Therefore, this method could be slower for larger arrays.

Using Recursion

static int binarySearch(int[] arr, int key, int start, int end){
   if(start > end){
      return -1;
   }
   int middle = (start+end)/2;
   if(arr[middle] == key){
      return middle;
   }
   if(arr[middle] > key){
      return binarySearch(arr, key, start, middle-1);
   }
   else {
      return binarySearch(arr, key, middle+1, end);
   }
}

4. Binary search efficiency

Binary Search time complexity is O(log(n)). In the best-case scenario, binary search has the efficiency of O(1) and O(log (n)) in the worst-case scenario.

For an array of 8 elements:
In every iteration we devide the array by 2, therefore log2 of 8
O(log (n)) => O(log2 (8)) => 3
Maximum of 3 iterations to find the key
For an array of 18 elements:
O(log (n)) => O(log2 (16)) => 4
Maximum of 4 iterations to find the key

Conclusion

Binary search works only on sorted arrays. Binary search operates by dividing the array into half in every iteration, therefore called Binary Search. In every division, the algorithm narrows down the search context and discards the array portion that does not contain the search key.