发表时间:2010-04-27
最后修改:2010-04-27
有序数组二分查找的基本原理:因为数组是有序的,先找到中间位置的值,如果目标比这个值大,那么该目标必定在数组的右半部分,以此循环或者递归,一直找到这个数值为止。此算法的时间复杂度为O(logN),N为数组的长度
package algorithm.arrayfind;
public class SortedArrayBinarySearch {
public static void main(String[] args) {
int[] source=new int[]{1,3,5,7,9,12};
int key = 12;
System.out.println(binaryRecurSearch(source, key));;
System.out.println(binarySearchLoop(source, key));;
}
public static int binaryRecurSearch(int[] source, int key){
return binarySearchRecursive(source, key,0,source.length-1);
}
private static int binarySearchRecursive(int[] source, int key,int beginIndex,int endIndex){
int midIndex = (beginIndex+endIndex)/2;
if(key<source[beginIndex]||key>source[endIndex]||beginIndex>endIndex){
return -1;
}
System.out.println("=======");
if(key == source[midIndex]){
return midIndex;
}else if(key > source[midIndex]){
return binarySearchRecursive(source, key, midIndex+1, endIndex);
}else{
return binarySearchRecursive(source, key, beginIndex, midIndex-1);
}
}
public static int binarySearchLoop(int[] source, int key){
int beginIndex = 0;
int endIndex = source.length-1;
while(true){
System.out.println("=======");
if(key<source[beginIndex]||key>source[endIndex]||beginIndex>endIndex){
return -1;
}
int midIndex = (beginIndex+endIndex)/2;
if(key == source[midIndex]){
return midIndex;
}else if(key > source[midIndex]){
beginIndex = midIndex +1;
}else{
endIndex = midIndex -1;
}
}
}
}