二分查找理解
二分查找
示例代码
int binarySearch(int arr[], int l, int r, int x)
{
if(r >= l) {
int mid = l + (r - l) / 2; // 计算中间索引
// 如果元素正好在中间位置
if (arr[mid] == x)
return mid;
// 如果元素大于中间元素，则在右半部分继续查找
if (arr[mid] < x)
return binarySearch(arr, mid + 1, r, x);
// 否则，在左半部分继续查找
return binarySearch(arr, l, mid - 1, x);
}
// 没有找到元素
return -1;
}
虽然很简单，但是有几个值得一提。
我们不妨认为二分是区间缩小，每次查找少一半的区间，来看以下特性
- 凡是存在整形截断的编程语言，二分查找，最后必然左端点，右端点汇聚在同一个点。也就是只剩下一个值。 原因也很简单，任意一个大于1的数，不断/2，在有整形截断的情况下，最后必然有结果是1。
有了二分查找，不如进一步思考，如果求这个数所在该数组的最小区间呢？
- 判出条件自然就是需要改变，R>L
- 然后就是L取mid+1，或者是R取mid-1的问题了，如何抉择呢？
- 实际上，L取mid+1,就是不断让L向前移动，R取mid，那么就保证R所在的值是大于于目标值。且由于整型截断，R与L之间即使只相差1，也会在mid计算时总是计算的是整个区间中间值左边的那一个，这样使得必然是L=mid+1,而使得L与R重合（L=R），让对应的值是 区间是[ arr[R-1],arr[R] ]
- 对应的，你如果取R是mid-1，L=mid,就可能导致死循环，因为整型截断，导致mid=L，而L与R的值相差1时，mid永远时L。
int binarySearch(int arr[], int l, int r, int x)
{
if(r > l) {
int mid = l + (r - l) / 2; // 计算中间索引
// 如果元素正好在中间位置
if (arr[mid] == x)
return mid;
// 如果元素大于中间元素，则在右半部分继续查找
if (arr[mid] < x)
return binarySearch(arr, mid , r, x);
// 否则，在左半部分继续查找
return binarySearch(arr, l, mid - 1, x);
}
// 没有找到元素
return -1;
}
当你了解了上面的知识，不妨看看下面这个题，思考一下如何用二分操作呢
在排序数组中查找元素的第一个和最后一个位置
答案:
class Solution {
public:
//这种二分返回的就是第一个小于目标值的下标
int binaryFind(vector<int>& nums,int target)
{
if(nums.empty()) return -1;
int l = 0,r = (int)(nums.size())-1;
while(l<r)
{
int mid = (l+r)>>1;
if(nums[mid] >= target)
{
r = mid;
}
else
{
l = mid +1;
}
}
if(nums[l] >= target)
{
return l-1;
}
return l;
}
vector<int> searchRange(vector<int>& nums, int target) {
int r = binaryFind(nums,target+1), l = binaryFind(nums,target);
if(l>=r)
{
return {-1,-1};
}
return {l+1,r};
}
};
思考上面代码核心思维，起始就是利用二分时下标的整形截断，使得最终求出来的那个值总是我们求值的最左边一个值，因此再对二分函数稍作处理，将其改为返回其刚好小于那个值的下标，整个函数封装的就很漂亮勒。
寻找两个正序数组的中位数
这题本身二分查找的思路并不难，难得是将其和两个数组正确的下标处理结合起来
题解的核心:
1.假设mid1是nums1的一个数的下标，mid2同理，合理中位数划分是 0-mid1-1,和0-mid2-1这些数字来作为左边半个部分，这样中位数就是左边半个部分的最大值，和右边半部分的最小值，根据奇偶情况算一下而已。
2.假设我们决定了mid1的值，mid2如何计算呢？m = nums1.size,n = nums2.size
根据判断，mid1左边显然有mid1个数字，那么mid2左边就应该：(m+n+1)/2 -mid1
A.我们总是让对应划分数字时，小的那部分， 0-mid1-1,和0-mid2-1后面称之为leftpart(rightpart类似)，leftpart应该再偶数： （m+n）/2 - mid1,奇数我们总是把多的数字给leftpart。
B. 有了A的基础，那么m+n是奇数的时候，所以左边要多分一个，所以公式就是(m+n+1)/2-mid1，
我们发现B的公式用于A情况，由于整形截断使不需要做调整的。注意，由于奇数我们给得leftpart多了一个值，那么最后奇数取得就是左边最大值，当然你也可以自行调整。
3.接下来我们看的就是，leftpart的个数解决了，我们要看这次分配是否合理把，就关键看mid-1下标的值是否比mid2的值还要大，如果更大，说明违反了左边值应该都比右边小的原则那么舍去，说明这次取的值太大了，应当缩小mid1,反之就是可能合理的mid1,应当接着扩大mid1，那么根据大小来操作，自然就是对mid1进行二分操作了。
4.我们上面处理的时候发现，mid2可能取超出n对吧，如果nums1太大就会出现这种情况，m=1,n=0情况,那么mid2不就是取1了么？所以我们不要让nums1大于nums2避免这种情况。
5.接着还有一个情况，那就是nums1为空，或者是nums1的值全部比nums2还要小这种情况，因此我们二分nums1，需要能取到m这个值，同时用m这个下标来标识一个最大值，这样好处就是取右边最小值不会有影响，同时我们要取mid1-1的值，那么mid1是0了呢？那么为了不影响左边最大值的取值，就应该使得mid1-1对应的值是INT_MIN。这些道理对nums2是一样的。
6.我们开始从第三步做二分操作，每次注意上面几点即可解决，left总是再变大之后，肯定是更加合适leftpart的，
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size())
nums1.swap(nums2);
int m = nums1.size(), n = nums2.size();
int left = 0,
right =
m; // 这里right需要取m,有可能第一个数组比第二个数组最小值都小或者空是可能的
int ans_mid1 = 0, ans_mid2 = 0;
while (left <= right) {
int mid1 = (left + right) >>1;
int mid2 = (m + n + 1) / 2 - mid1;
int mid1_1_val = (mid1 ==0 ? INT_MIN:nums1[mid1-1]);
int mid1_val = (mid1 == m ? INT_MAX : nums1[mid1]);
int mid2_1_val = (mid2 == 0 ? INT_MIN : nums2[mid2 - 1]);
int mid2_val = (mid2 == n ? INT_MAX : nums2[mid2]);
// 接着判断这次值是否可能合理,mid1-1对应的值掯定比mid1的值小，因此直接和mid2比较即可
if (mid1_1_val <= mid2_val) {
ans_mid1 = max(mid1_1_val, mid2_1_val);
ans_mid2 = min(mid1_val, mid2_val);
left = mid1 + 1;
} else {
right = mid1 - 1;
}
}
return (m+n)%2?ans_mid1:(ans_mid1+ans_mid2)/2.0;
}
};