CodesJava

Easy learning with example program codes

Java binary search program using recursion


Search algorithm

Search algorithm refers to a step-by-step procedure which is used to locate specific data among a collection of data. All search algorithms use a search key in order to proceed for the search operation. The efficiency of a search algorithm is measured by the number of times a comparison of the search key is done in the worst case. The notation used in search algorithms is O(n), where n is the number of comparisons done.

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.codesjava;
 
public class Test {
    public static int binarySearch(int[] data,int start, int end,int key){    
        if (start < end) {
            int mid = start + (end - start) / 2;  
            if (key < data[mid]) {
                return binarySearch(data, start, mid, key);
 
            } else if (key > data[mid]) {
                return binarySearch(data, mid+1, end , key);
 
            } else {
                return mid;   
            }
        }
        return -(start + 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,0, data.length, key));  
   }
}

Output

130 is found at index: 2
Sign Up/ Sign In
Ask a Question


Copyright © 2018 CodesJava DMCA.com Protection Status SiteMap Reference: Java Wiki