思路: 先划分空间,再在其空间查找,取中间点,中间点往左,元素的值一定比中间值小,右边的值一定比中间值大.
判断 关键点 if (key>arr[mid]) {low = mid+1;} //右半区查找
if (key<arr[mid]){high = mid - 1;} //左半区查找
找 12
low high
0 1 2 3 4 5 6 7 8 9
// 3 4 12 20 21 23 28 45 67 100
--------------------------------------------
1 low mid high
2 low mid high
3 low high
mid = (low + high) / 2 = 4;
a[4] = 21 > 12 --> high = mid - 1 ---> 4 - 1 = 3
mid = (low + high)/2 = 1;
a[1] = 4 < 12 --> low = mid + 1 --> 1+1 = 2
mid = (2+3)/2 --> 2
a[2] = 12 == 12
//折半查找
int searchItem(int arr[],int len,int key){
//先要定义变量
int low=0,high=len-1,mid;
//循环
while (low<=high) {
// 计算 mid的位置
mid = (low+high)/2;
printf("mid = %d",mid);
// 判断 key a[mid],右半区查找
if (key>arr[mid]) {
// key > a[mid] low = mid +1;
low = mid+1;
}else if (key<arr[mid]){
// key < a[mid] high = mid -1;
high = mid - 1;
}else{
// key == a[mid] //return mid;
return mid;
}
}
// 下面是查找不到的情况
return -1;
}
//折半插入 不建议看
int insertItemLoc(int arr[],int len,int key){
//先要定义变量
int low=0,high=len-1,mid;
//循环
while (low<=high) {
// 计算 mid的位置
mid = (low+high)/2;
// 判断 key a[mid],右半区查找
if (key>arr[mid]) {
// key > a[mid] low = mid +1;
low = mid+1;
}else if (key<arr[mid]){
// key < a[mid] high = mid -1;
high = mid - 1;
}else{
// key == a[mid] //return mid;
return mid + 1;
}
}
// 下面是查找不到的情况
return low;
}
|
|
收藏
淘帖
踩
