算法（Java）——⼆分法查
算法相关数据结构总结：
序号数据结构⽂章
1动态规划
3链表
4⼆叉树
5哈希表
6字符串
7栈和队列
8贪⼼算法
9回溯
基因调控网络10⼆分查
11双指针、滑动窗⼝
在排序数组中，⼆分法查是⼀种⾼效率⽅法。
⼆分法查，也称为折半法，是⼀种在有序数组中查特定元素的搜索算法。
⼆分法查的思路如下：
1. ⾸先，从数组的中间元素开始搜索，如果该元素正好是⽬标元素，则搜索过程结束，否则执⾏下⼀步。
2. 如果⽬标元素⼤于/⼩于中间元素，则在数组⼤于/⼩于中间元素的那⼀半区域查，然后重复步骤（1）的操作。科研能力评价
谐波传动3. 如果某⼀步数组为空，则表⽰不到⽬标元素。
⼆分法查的时间复杂度O(logn)。
⼆分法查
⼆分法查的实现
⾮递归算法：
function binarySearch(arr,key){
var low=0;//数组最⼩索引值
var high=arr.length-1;//数组最⼤索引值
滚子链联轴器while(low<=high){
var mid=Math.floor((low+high)/2);
if(key==arr[mid]){
return mid;
}else if(key>arr[mid]){
low=mid+1;
}else{
high=mid-1;
}
}
return-1;//low>high的情况，这种情况下key的值⼤于arr中最⼤的元素值或者key的值⼩于arr中最⼩的元素值
}
递归算法：
function binarySearch(arr,low,high,key){
if(low>high){return-1;}
var mid=Math.floor((low+high)/2);
if(key==arr[mid]){
return mid;
}else if(key<arr[mid]){
high=mid-1;
return binarySearch(arr,low,high,key);
}else{
low=mid+1;
return binarySearch(arr,low,high,key);
如梦令赏析
}
}
⼆分法查的细节
从⼆分法的实现，我们可能觉得⼆分法查很简单，但细节是魔⿁。
我们就是要深⼊细节，⽐如while循环中的不等号是否应该带等号，mid 是否应该加⼀等等。
⼆分查的框架
int binarySearch(int[] nums,int target){
int left =0, right =...;
while(...){
int mid =(right + left)/2;
if(nums[mid]== target){
...
}else if(nums[mid]< target){
left =...
}else if(nums[mid]> target){
right =...
}
}
<;
}
声明⼀下，计算 mid 时需要技巧防⽌溢出，建议写成: mid = left + (right - left) / 2，这个在很多算法题的解析中都已经注意写法了。寻⼀个数（基本的⼆分搜索）
int binarySearch(int[] nums,int target){
int left =0;
int right = nums.length -1;// 注意
while(left <= right){// 注意
int mid =(right + left)/2;
if(nums[mid]== target)
return mid;
else if(nums[mid]< target)
left = mid +1;// 注意
else if(nums[mid]> target)
right = mid -1;// 注意
}
return-1;
}
为什么 while 循环的条件中是 <=，⽽不是 < ？
因为初始化 right 的赋值是 nums.length - 1，即最后⼀个元素的索引，⽽不是 nums.length。
区别是：前者相当于两端都闭区间 [left, right]，后者相当于左闭右开区间 [left, right)，因为索引⼤⼩为 nums.length 是越界的。
为什么 left = mid + 1，right = mid - 1？我看有的代码是 right = mid 或者 left = mid，没有这些加加减减，到底怎么回事，怎么判断？
当我们发现索引 mid 不是要的 target 时，如何确定下⼀步的搜索区间呢？
当然是去搜索 [left, mid - 1] 或者 [mid + 1, right] 对不对？因为 mid 已经搜索过，应该从搜索区间中去除。
注：
1. 初始化right=nums.length-1，则while(left<=right),right=mid-1
2. 初始化right=nums.length，则while(left<right),right=mid
⼒扣关于⼆分法查的题
题⽬：统计⼀个数字在排序数组中出现的次数。
解题思路：排序数组nums中的所有数字target形成⼀个窗⼝，窗⼝左右边界对应左右边⾸个元素。⼆分法查左右边界，根据左边界判断等与target的个数。
算法代码：
class Solution {
public int search(int[] nums,int target){
int l=0,r=nums.length-1;
int count=0;
while(l<=r){
int m =(l+r)/2;
if(nums[m]<target) l=m+1;
else r=m-1;
}
while(l<nums.length&&nums[l++]==target){
count++;
}
return count;
}
}
2）剑指offer53_Ⅱ。0~n-1中缺失的数字
题⽬：⼀个长度为n-1的递增排序数组中的所有数字都是唯⼀的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有⼀个数字不在该数组中，请出这个数字。
解题思路：递增有序的查，就是考⼆分查，⽐较nums[m]和m是否相等。阴道血管肉瘤
算法代码：
class Solution {
public int missingNumber(int[] nums){
int i=0,j=nums.length-1;
while(i<=j){
int m=i+(j-i)/2;
if(nums[m]==m) i=m+1;
else j=m-1;
}
return i;
}
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议