简单的二分查找
1.简介
这里所讲解的简单的二分查找指的是在一个有序无重复元素的int类型的数组中查找需要的元素。
2.代码
public int binarySearch(int[] a ,int value){
int low = 0, hi = a.length - 1;
while(low <= hi){
int mid = low + ((hi - low)>>1);
if(a[mid] == value){
return mid;
}else if(a[mid] < value){
low = mid + 1;
}else if(a[mid] > value){
hi = mid - 1;
}
}
return -1;
}
代码分析
举例:数组
int[] a = {2,3,5,7,8,10};
-
low <= hi
在进行二分查找的时候,当低位指针和高位指针相遇时,如果还没有找到要找的元素,这个时候就可以跳出循环了。 -
low = mid + 1
low不能mid(low=mid),假设low=mid,hi=mid - 1;当我们要找的元素 value >= max(数组中最大的元素),我们会找不到元素,也无法跳出循环 以举例数组为例,当我们要找 10 时,当 low = mid 这一步使 low = 4时;这时 low<=hi, int mid = low + ((hi - low)>>1) = 4, 这时mid的值没法再增加,low也会一直为4,虽然数组中有10,但是我们无法跳出循环,也无法找到10。 -
hi = mid - 1
hi不能为mid(hi=mid),假设 low = mid + 1 , hi = mid;当我们要找的元素 value < min(数组中最小的元素),数组中没有元素,但是无法跳出循环。以举例数组为例,当我们要找1时, 当 hi = mid 这一步使 hi = 0时;这时 low<=hi,int mid = low + ((hi - low)>>1) = 0, 这时 mid的值没法再减小, hi也会一直为0,虽然数组中没有1,但是无法跳出循环。
总结
在对一个有序无重复的int数组进行二分查找的时候,就是不断的折半,直到高低位指针相遇跳出循环。还有要注意的就是当折半后low = mid + 1和hi = mid - 1 这些小细节。
上一篇: 路由的前置路由守卫和后置路由守卫