Java binary search program

by

Binary search

Binary search is a search algorithm that finds the position of a target value within a sorted collection of data (we are taking array here). It is a fast search algorithm with run-time complexity of Ο(log n). It works on the principle of divide and conquer.

Binary search compares the target value to the middle element of the array; if they are unequal, the half in which the target cannot lie is eliminated and the search continues on the remaining half until it is successful. If the search ends with the remaining half being empty, the target is not in the array.

Basic algorithm

Given an array A of n elements with values or records A0, A1, …, An−1, sorted such that A0 ≤ A1 ≤ … ≤ An−1, and target value T, the following subroutine uses binary search to find the index of T in A.

  • Set L to 0 and R to n − 1.
  • If L > R, the search terminates as unsuccessful.
  • Set m (the position of the middle element) to the floor (the largest previous integer) of (L + R) / 2.
  • If Am < T, set L to m + 1 and go to step 2.
  • If Am > T, set R to m − 1 and go to step 2.
  • Now Am = T, the search is done; return m.

This iterative procedure keeps track of the search boundaries with the two variables.

Example

package com.w3schools;
 
public class Test {
  public static int binarySearch(int[] data, int key){    
	int start = 0;
        int end = data.length - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            if (key == data[mid]) {
                return mid;
            }
            if (key < data[mid]) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return -1;  
    }    
 
    public static void main(String args[]){
	int[] data= {50,127,130,150,170,910,1009};    
        int key = 130;    
        System.out.println(key+" is found at index: "+binarySearch(data, key));  
   }
}

Output

130 is found at index: 2