Binary Search Implementation in Java

• Binary Search in Java
  • Java Program for Binary Search
  • Pros and Cons of Binary Search
  • Analysis of Binary Search
• References

Binary Search in Java

Binary search operates on a sorted list and finds the given element by comparing it with the middle element of the list. The comparison determines whether the middle element is equal to the given element, less than the input or greater. Binary search delivers better performance than sequential search by sorting the elements of the list ahead of searching.

Binary search looks at the middle element of the list and see if the element sought-for is found. If not, than it compares the sought-for element with the middle element of the list and check whether the middle element is larger than the element we are trying to find. If so, we keep looking in the first half of the list; otherwise, we look in the second half. It cuts the number of elements to be compared by half. We keep going in the same way until the item is found or it is determined that the sought-for element is not present in the list.

The input to binary search is an indexed collection A of elements. Each element A[i] has a key value k_i that can be used to identify the element. These keys are totally ordered, which means that given two keys, k_i and k_j, either k_i<k_j, k_i==k_j, or k_i>k_j.

Java Program for Binary Search

Given an ordered collection of elements as an array, the following program develops a class BinarySearch that contains a parameterized static method binarySearch for any base type T. Note that Java provides the java.util.Comparable interface that contains a single method, compareTo. Any class that correctly implements this interface guarantees a total ordering of its instances.

import java.util.*;
class BinarySearch 
{
  /* Apply binary search to search the sorted list (of type T) for the given item. */
  public static <T extends Comparable<T>> boolean binarySearch (T[] list, T searchKey) 
  {
    // null is never included in the list
    if (searchKey == null) 
    { 
      return false; 
    }
    int low = 0, high = list.length - 1;
    while (low <= high) 
    {
      int mid = (low + high)/2;
      int rc = searchKey.compareTo(list[mid]);
      if (rc < 0) 
      {
        // searchKey is less than list[i]
        high = mid - 1;
      } 
      else if (rc > 0) 
      {
        // searchKey is greater than list[i]
        low = mid + 1;
      } 
      else 
      {
        // found the item.
        return true;
      }
    }
    return false;
  }
}
 
public class BinarySearchDemo
{
  public static void main (String[] args)
  {
    Integer arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    Integer searchKey = new Integer("7");
 
    /* Uses binary search and search through the sorted list */ 
    System.out.println("Search key " + searchKey + " is found? " + BinarySearch.binarySearch (arr, searchKey));
  }
}
 
OUTPUT
======
Search key 7 is found? true

Above binary search implementation in Java uses three important variables: low, high, and mid. low is the lowest index of the current sub-array being searched, high is the upper index of the same sub-array, and mid is the midpoint of the sub-array.

Pros and Cons of Binary Search

Binary search adds a small amount of complexity for large performance gains. The complexity can increase when the collection is not stored in a simple in-memory data structure, such as an array. There must be a way to access element A[i] for 0 <= i < n in the collection based upon the natural order of the elements in the collection, as represented by the Comparable interface. A large collection might need to be kept in secondary storage, such as a file on a disk. In such a case, the i^th element is accessed by its offset location within the file. Using secondary storage, the time required to search for an element is dominated by the costs to accessing the storage; other solutions related to binary search may be appropriate.

Analysis of Binary Search

Binary search divides the problem size approximately in half every time it executes the loop. The maximum number of times the collection of size n is cut in half is log(n), if n is a power of 2; otherwise, it is ⌊log(n)⌋. If we use a single operation to determine whether two items are equal, lesser than, or greater than (as is made possible by the Comparable interface), then only ⌊log(n)⌋ comparisons are needed, resulting in a classification of O(log n).

Last Word

In this tutorial we discussed binary search algorithm and implemented it through a Java program. Hope you have enjoyed reading this tutorial. Please do write us if you have any suggestion/comment or come across any error on this page. Thanks for reading!

References