Implementing Binary Search in Java

Hello friends, In this tutorial, we will study the searching technique called Binary Search and its implementation in Java.

Binary Search is one of the most efficient searching techniques used to search for a key element in a sorted array as it repeatedly divides the array to half.

First, we calculate the mid element to divides the array into two parts.
Further, we check if the key is less than the mid element if it is true we search in the first half of the array because as the array is sorted all the elements in the other half will be greater than the key element.
Similarly, if the key is greater than the mid element we search in the second half of the array because all the elements in the first half will be smaller than the key elements.

We repeat the process until

1. A key element is found and hence returns the index of the key element.

 OR

2. Lower index is greater than the higher index which indicates that the key element we are searching for is absent in the array.

Hence for the best case, the time complexity of binary search is O(1) whereas for the average and worst-case it is O(log n).

For example:

NOTE: For performing a binary search, the array should be sorted.

Algorithm:

1. Set low=0 and high=n-1
2. If low > high stop searching.
3. Set mid = (low + high)/2.
4. If mid = key –> go to Step 7.
5. If mid < key –> Set high = mid-1 –> go to Step 2.
6. If mid > key –> Set low = mid+1 –> go to Step 2.
7. Return mid and STOP.

Implementation of Binary Search in Java

Let us now write the code for binary search in Java.
The binarySearch function takes two parameters, first is the array, and the second is the key element that we are searching in the array.

public static int binarySearch(int[] arr, int key)
{
    int low=0;
    int high=arr.length-1;
    while(low<=high)
    {
      int mid=(low+high)/2;
      // if value at mid index is equal to key search is successfull
      if(arr[mid]==key)  
      {
        return mid;
      }
      else if(arr[mid]<key)
      {
        low=mid+1; // to search in the second half of array
      }
      else
      {
        high=mid-1; // to search in the first half of the array
      }
    }
        return -1; // key element not found   
}

Our function returns the index of the key element. If the key is not found we return -1.

Main function:

In the main function, we call the binarySearch function by sending the array and the key element as function parameters.
Index variable stores the integer value returned by the function.

public static void main(String args[])
{
  int arr[]= {5,10,15,20,25,30,35,40};
  int key=15;
  int index=binarySearch(arr,key);
  if (index<0)
  {
    System.out.println("Key not found in array");
  }
  else
  {
    System.out.println("Key found at index "+index);
  }
}

Following is the output of the above java code

Output:

Key found at index 2