Binary Search Implementation in Java

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 ki that can be used to identify the element. These keys are totally ordered, which means that given two keys, ki and kj, either ki<kj, ki==kj, or ki>kj.

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 ith 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




Get Free Tutorials by Email

About the Author

is the main author for cs-fundamentals.com. He is a software professional (post graduated from BITS-Pilani) and loves writing technical articles on programming and data structures.

Today's Tech News

AlphaBay and Hansa dark web markets shut downPosted on Thursday July 20, 2017

The AlphaBay and Hansa marketplaces were known for trade in drugs, weapons and malware.

Bitcoin swings as civil war loomsPosted on Thursday July 20, 2017

The Bitcoin community must agree how to tackle a slowdown in transaction times to avoid a schism.

Google Maps adds the International Space StationPosted on Thursday July 20, 2017

The International Space Station becomes the first "off planet" addition to the interactive tool.

Courtesy BBC News

AD BLOCKER DETECTED!

Advertisements help running this site for free.


To view the content please disable AdBlocker and refresh the page.

×