基本前提：
- 数组已经按照升序排列
- 同时数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的
基本原理：
首先将要查找的元素key和数组的中间元素mid比较
1.如果key<mid值，只需要在数组前一半元素中继续查找
2.如果key=mid值，匹配成功，查找结束
3.如果key>mid值，只需要在数组后一半元素中继续查找
通过调节 left 和 right 就可以调整每一轮 sum 的长度。
例：假设要寻找元素5
初始low=0；high=数组的length-1
假设5< mid ，需要去数组前一半去查找，则high=mid-1，即搜索区间变为 [lo,mid-1] √
假设5> mid ，需要去数组后一半去查找，则low=mid+1，即搜索区间变为 [mid+1，high]
更新mid=2，值为8
更新mid=(0+1)/2=0, 值为2; 此时mid=lo
再比较，5>mid值；lo=mid+1=1;
更新mid=(1+1)/2=1; 此时 mid=5，搜索结束。
Java实现：
int bi(int[] nums,int val){
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(val == nums[mid]){ // 每一轮先判断
System.out.println("bingo");
return mid;
}else if(nums[mid]>val){
right=mid-1;
}else if(nums[mid]<val){
left=mid+1;
}
}
return -1;
}
}
注意：
二分查找不要出现else，而是把所有的情况用else if 写清楚
总结：
前提是给定有序单调递增的数组
取数组中间元素mid
由于一开始数组里面有n个元素，
折半一次还有n/2，折半k次之后是n/2^k
所以二分法复杂度时间是O(log n)
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89309.html
