两种： 循环或递归
- 循环 详细戳这里
public static int binarySearch(int searchKey,int[] array){
int low=0;
int high=array.length-1;
while (low<=high){
int middle=(low+high)>>1;
if (searchKey==array[middle]){
return middle;
}else if (searchKey<array[middle]){
high=middle-1;
}else {
low=middle+1;
}
}
return ~low;
}
- 递归
调用：binarySearchRecursion(key,a,0,a.length)
public static int binarySearchRecursion(int searchKey,int[] array,int lowIndex,int highIndex){
if (searchKey<array[lowIndex] || searchKey>array[highIndex] || lowIndex>highIndex){
return ~lowIndex;
}
int middleIndex=(lowIndex+highIndex)>>1;
if (searchKey<array[middleIndex]){
return binarySearchRecursion(searchKey,array,lowIndex,middleIndex-1);
}else if (searchKey>array[middleIndex]){
return binarySearchRecursion(searchKey,array,middleIndex+1,highIndex);
}else {
return middleIndex;
}
}
