概述
认识二分法
经常见到的类型是在一个有序数组上，开展二分搜索。但有序确不一定是使用二分的必要条件。
只要能够正确构建左右两侧的淘汰逻辑，就可以二分。
算法时间复杂度
O(logN)，logN是指㏒₂N（log以2为底的对数）。
二分查找代码实现
public static boolean exist(int[] arr, int num) {
if (Objects.isNull(arr) || arr.length < 1) {
return false;
}
int left = 0;
int right = arr.length - 1;
int middle = 0;
// left < right 保证有两个数才进行二分
while (left < right) {
// 就是(right + left)/2，但是这样有溢出风险;
// (right -left) >> 1 就是(right -left)/2，这样速度更快，位运算比/更快
middle = left + ((right - left) >> 1);
if (arr[middle] == num) {
return true;
} else if (arr[middle] > num) {
// 砍掉右边
right = middle - 1;
} else {
// 砍掉左边
left = middle + 1;
}
}
// 因为上面是至少两个数才二分，这里比较一个数的情况(left == right)
return arr[left] == num;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99950.html
