Monday, January 27, 2014

Optimal Binary search java code


Binary search looks so simple but when we tried to implement we will face many problems.I googled a lot for optimal code but I could not able to find. So here I am posting one which is well optimized and a perfect java code for binary search.


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BinarySearch {

/**
* @author Rajesh Barri
*/
public static void main(String[] args) {
// TODO Auto-generated method stub

List<Integer> list = new ArrayList<>(Arrays.asList(1,3,4,5,2,3,3));
Collections.sort(list);
int search=2;
System.out.println(list);
System.out.println(binSearch(list, 0, search));

}


public static int binSearch(List<Integer> list, int first,int val){
      int len = list.size();
      while (len > 0){
     int half = len >> 1;
     int middle = first+half;

     if (middle < val){
     first = middle;
     ++first;
     len = len - half - 1;
     }
     else
     len = half;
      }
      return first;
}
}

1 comment:

  1. Good going rajesh, a perfect and optimal code. Remember, to test if the element is found, you got to test the offset for the value you are searching.

    ReplyDelete