二分查找
本页目录
需求：在有序数组A中，查找值target。如果找到了，返回target的索引，如果找不到返回-1
二分查找 基础版
解决思路：定义3个元素：左边界、有边界、中间索引。
public class 二分查找 {
// 前置了解：二分法，核心是获取中间索引，比如5个元素，中间的索引是2，(int)5/2 正好是2哦
// 有3个重要元素：左边界、有边界、中间边界。其中参与对比的是中间边界。
public static void main(String[] args) {
int target = 3; // 定义目标元素
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int leftIndex = 0; // 定义左边界
int rightIndex = a.length - 1; // 定义右边界
int middleIndex; // 定义中间边界
int count = 0; // 自己搞一个计数器
while (leftIndex <= rightIndex) { // 左边界必须要小于等于右边界。
count++;
middleIndex = (leftIndex + rightIndex) / 2;
if (a[middleIndex] < target) { // 目标在右边，左边逼近一位
leftIndex = middleIndex + 1;
} else if (target < a[middleIndex]) { // 目标在左，右边逼近一位
rightIndex = middleIndex - 1;
} else { // 命中元素
System.out.println("命中的索引是"+middleIndex);
break;
}
}
System.out.println("总共循环了" + count + "次");
}
}二分查找 基础班 优化点：无符号右移运算符>>>
middleIndex = (leftIndex + rightIndex) / 2;这个代码看似没问题，第一次leftIndex是0，rightIndex三21亿，想加后再除以2，没问题。如果第二次是设置左边界使得leftIndex变成非0，就会导致(leftIndex + rightIndex) 超过21亿的范围，经过计算，再除以2最终的结果就是（在Java中会把最高位定义为符号位）负数。请选择使用位运算>>>1 相当于除2。
第一位是符号位，1是负数，0是整数，原来是1的，右移1位，就被0代替了。不管如何，只要右移，结果都是整数！只要保证结果是正数，都可以使用无符号右移1位！
middleIndex = (leftIndex + rightIndex) >>> 1;二次查找 改动版
这一版本毫无意义。定义右边界不起命中作用，只用leftIndex 通过+1 去一步步逼近元素！如果+1 之后大于rightIndex，循环结束，没有命中目标！
public class 二分查找改动版 {
// 前置了解：二分法，核心是获取中间索引，比如5个元素，中间的索引是2，(int)5/2 正好是2哦
// 有3个重要元素：左边界、有边界、中间边界。其中参与对比的是中间边界。
public static void main(String[] args) {
int target = 3; // 定义目标元素
int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int leftIndex = 0; // 定义左边界
int rightIndex = a.length; // 定义右边界
int middleIndex; // 定义中间边界
int count = 0; // 自己搞一个计数器
while (leftIndex < rightIndex) { // 左边界必须要小于右边界
count++;
middleIndex = (leftIndex + rightIndex) >>> 1;
if (a[middleIndex] < target) { // 目标在右边，左边逼近一位
leftIndex = middleIndex + 1;
} else if (target < a[middleIndex]) { // 目标在左，右边逼近一位
rightIndex = middleIndex;
} else { // 命中元素
System.out.println("命中的索引是"+middleIndex);
break;
}
}
System.out.println("总共循环了" + count + "次");
}
}总结：使用基础版本即可，改动版毫无意义！本文当前的基础版其实还有优化点，循环判断的时候，直接判断是否命中元素，如果命中元素直接返回！不需要先判断左边界、右边界！嘿嘿，我知道，但我就不改！本站ChatGPT：你问问给我来份Java最优二分查找代码，也行！
特殊说明： 第三方平台不会及时同步本文章最新内容，如果觉得本文资料不全，可以访问本人Java博客搜索：标题类似的关键字 上述文章均是我实际操作后产出，烦请各位，请勿直接盗用！转载记得标注原文链接：www.zanglikun.com
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录