二分查找
- 摘要:二分查找数组必须为有序数组,查找速度比无序数组快,插入速度比无序数组慢。查找次数为数组长度的开方。方法:publicstaticintfind(longsearchKey){long[]arr=newlong[100];arr[0]=11;arr[1]=22;arr[2]=33;arr[3]=44;arr[4]=55;arr[5]=66;arr[6]=77;arr[7]=88;arr[8]=99;arr[9]=100;intcountElems=10;intlowerElem=0
- 标签:查找
二分查找数组必须为有序数组,查找速度比无序数组快,插入速度比无序数组慢。
查找次数为数组长度的开方。
方法:
public static int find(long searchKey) {
long[] arr = new long[100];
arr[0] = 11;
arr[1] = 22;
arr[2] = 33;
arr[3] = 44;
arr[4] = 55;
arr[5] = 66;
arr[6] = 77;
arr[7] = 88;
arr[8] = 99;
arr[9] = 100;
int countElems = 10;
int lowerElem = 0;
int upperElem = countElems - 1;
int currIn;
while (true) {
currIn = (lowerElem + upperElem) / 2;
if (arr[currIn] == searchKey) {
return currIn;
} else if (lowerElem > upperElem) {
return countElems;
} else {
if (arr[currIn] < searchKey) {
lowerElem = currIn + 1;
} else {
upperElem = currIn - 1;
}
}
}
}
调用:
public static void main(String[] args) {
long a = find(111);
System.out.println(a);
}