Skip to content

Instantly share code, notes, and snippets.

@bitcpf
Created September 18, 2014 02:17
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save bitcpf/c5335fa99b5030343135 to your computer and use it in GitHub Desktop.
Save bitcpf/c5335fa99b5030343135 to your computer and use it in GitHub Desktop.
import java.util.Arrays;
public class Q_3 {
public static int magicBS(int[] array, int start, int end){
if(end < start || start <0 || end >= array.length){
return -1;
}
int mididx = (start+end) / 2;
int midval = array[mididx];
if(array[mididx] == midval){
return mididx;
}
// Left Search
int leftidx = Math.min(mididx - 1,midval);
int left = magicBS(array,start,leftidx);
if(left >= 0){
return left;
}
// Right Search
int rightidx = Math.max(mididx + 1,midval);
int right = magicBS(array,rightidx+1,end);
return right;
}
public static void main(String[] args){
int[] testarray = new int[] {0,1,2,4,5,6,9};
System.out.println(Arrays.toString(testarray));
System.out.println(magicBS(testarray,0,testarray.length-1));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment