二分查找的不同实现方法和总结
二分查找
二分查找的基本思路
二分查找适用于什么情况？
二分查找用于其输入是有序的顺序存储结构（例如有序数组）
二分查找的基本思路
- 选中序列中心元素与查找目标元素比较
2.1 如果目标元素比较小：选择前面（小元素）区间中心元素再做比较 2.2 如果目标元素比较大：选择后面（大元素）区间中心元素再做比较 2.3 如果目标元素等于中心元素：返回元素所在位置- 如果查找完成仍未找到，返回null
二分查找代码实现（LeetCode704）
边界一：不断缩小范围，锁定元素，不能提前返回
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = l + r >> 1; //向下取整，中点靠左
if(nums[mid] >= target) r = mid; //包含mid取等号
else l = mid+1; //l往右加一
}
if(nums[l] == target) return l;
return -1;
}
};
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = l + r + 1 >> 1; //加一后中点会靠右
if(nums[mid] > target) r = mid - 1; //r往左减一
else l = mid;//包含mid取等号
}
if(nums[l] == target) return l;
return -1;
}
};
总结：二分的边界条件与快排类似，l+r>>1 对应于（mid,mid+1) ；l+r+1>>1 对应于（mid-1,mid) ，包含mid的区间取等号，他们都是基于分而治之的递归思想实现
边界二：每次判断中心点值是否与target相等，可以提前返回
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l <= r){
int mid = l + r >> 1;
if(nums[mid] > target) r = mid - 1;
else if (nums[mid] == target)return mid;
else l = mid + 1;
}
return -1;
}
};
二分查找另类用法（寻找小于或等于target的最大值/寻找大于或等于target的最小值
寻找大于或等于target的最小值
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = l + r >> 1; //向下取整，中点靠左
if(nums[mid] >= target) r = mid; //包含mid取等号
else l = mid+1; //l往右加一
}
return l;
}
};
寻找小于或等于target的最大值
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l < r){
int mid = l + r + 1 >> 1; //加一后中点会靠右
if(nums[mid] > target) r = mid - 1; //r往左减一
else l = mid;//包含mid取等号
}
return l;
}
};
