原创
java算法二分查找
1. 概念
二分查找又叫折半查找，要求待查找的序列有序，每次取中间位置的值与待查关键字比较，如果待查关键字比中间位置的值小，则在前半部分循环这个查找的过程，反之，在后半部分循环这个查找的过程。直到查到了为止，否则序列中没有待查的关键字。
2. 思路
① while 循环折半，什么时候停止？在不断折半的过程中，我们的目标区间是不断缩小的，当左边界开始大于右边界的时候就是循环应该停止的时候，在以下代码中，我用 left 表示左边界（初始值为0），right 表示右边界（初始值为数组长度减1）；
② 折半之后有个中间值，我们试图拿它来跟待查找关键字进行比对，因为待查找序列是从大到小排列的，当然是小的在左边大的在右边，通过比较中间值和待查找关键字的大小，我们就进一步缩小了查找的范围。下面我用 mid 作为中间值变量，它的位置为左边界与右边界之和除2；
③ 向右查找，即待查关键字大于中间值。这时候我们的右边界是不需要动的，左边界应是中间中间位置的下一位，即 mid + 1；
④ 向左查找，即待查关键字小于中间值。这时候左边界是不需要动的，右边界应是中间位置的上一位，即 mid - 1；
⑤ 什么情况下查找成功呢？当中间值恰好等于待查关键字的时候，查找成功。 返回 mid + 1；
⑥ 就那么确定你能查到？万一人家这个序列里根本就没有你要的这个数据呢？所以这里我们还要给出一个回应，能查到好说直接就结束程序，如果找到最后了也没找到，自然是要退出 while 循环的，然后给它返回一个 -1，代表我们并没有找到这个值。
3. 代码实现
public static int binarySearch(int[] data, int target){
int left = 0;
int right = data.length - 1;
int center;
while(left <= right){
center = (right+left) >>> 1;
if(data[center] == target){
return center;
}else if(data[center] > target){
right = center - 1;
}else{
left = center + 1;
}
}
return -1;
}
评论
测试
登录后才可以进行评论哦！