二分查找基础专题——二分模板二分查找基础专题——二分模

二分查找基础 1.前言以前总觉得得先把概念都过一遍完全理解了才能开始刷题，殊不知实践才是掌握知识的捷径，而不是背了忘忘了背。学知识本来就需要沉下心，一步一个脚印的走，否则在未来某个关键时刻会因当初的囫囵吞枣而受到惩罚。
【二分查找基础专题——二分模板】所以别想那么多，直接开刷就是了，先从简单的二分查找开始。但是有一说一，二分思想虽简单，但是处理细节需格外小心，否则容易导致死循环。
2.概念核心有序、折半查找、时间复杂度O(logN)
3.算法模板通常我们的算法题都不会直接让我们用二分求某个数，都需要我们根据实际情况转换一下。
二分题目通常分为两种类型：

第一种是查找第一个满足条件的下标，即00001111找第一个1的情况
第二种是查找最后一个满足条件的下标，即11110000找最后一个1的情况

/*模板一（左边为0右边为1），查找第一个1，00001111 * check(mid)意思为找到'1'，此时mid可能是右边任何一个'1'， * 即无法确定mid是否为第一个'1'，所以我们在向左边缩小范围时不能写成 * r=mid-1,要写成r=mid; * 同理，else情况为没找到'1'，所以向右边缩小范围，因为mid肯定不满足条件，所以l=mid+1 */int bsearch_1(int l, int r) { while (l < r) { int mid = l + r >> 1; if (check(mid)) r = mid; else l = mid + 1; } return l; }

/*模板二（左边为1右边为0），查找最后一个1，11110000 * check(mid)意思为找到'1'，此时mid可能是左边任何一个'1'， * 即无法确定mid是否为最后一个'1'，所以我们在向右边缩小范围时不能写成 * l=mid+1,要写成l=mid; * 同理，else情况为没找到'1'，所以向左边缩小范围，因为mid肯定不满足条件，所以r=mid-1 */int bsearch_2(int l, int r) { while (l < r) { int mid = l + r + 1 >> 1; //加1避免死循环 eg:10 if (check(mid)) l = mid; else r = mid - 1; } return l; }

4.Leetcode二分基础题目 69.Sqrt(x)
思路解析：
通常一个整数的平方根是一个无限不循环小数，依题意知要返回一个小于等于平方根的整数。换句话说，我们就只需要从小于等于平方根的整数中找到最大的那个整数，符合11110000找最后一个1的模型，即模板二。
最后注意下数据范围即可。

class Solution { public: int mySqrt(int x) { long long l = 0, r = x; while (l < r) { long long mid = l + r + 1 >> 1; if (mid * mid <= (long long)x) l = mid; else r = mid - 1; } return l; } };

35.搜索插入位置
思路解析：
由题意知没有重复的元素，故模板一、模板二都可以，这里使用模板一。这里要特殊考虑一下数组为空，或者查找元素小于、大于所有数组元素的情况。

class Solution { public: int searchInsert(vector& nums, int target) { int len = nums.size(); if (len == 0) return 0; if (nums[len - 1] < target) return len; if (nums[0] > target) return 0; int l = 0, r = len - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; } return l; } };

34.在排序数组中查找元素的第一个和最后一个位置
思路解析：
这个思路很清晰，先使用模板一00001111查找第一个1；然后从找到的第一个1开始使用模板二11110000查找最后一个1。

class Solution { public: vector searchRange(vector& nums, int target) { int len = nums.size(); if (len == 0) return {-1, -1}; vector vec; int l = 0, r = len - 1, st = 0, ed = 0; while (l < r) { int mid = l + r >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; }if (nums[l] == target) { st = l; int low = st, high = len - 1; while (low < high) { int mid = low + high + 1 >> 1; if (nums[mid] > target) high = mid - 1; else low = mid; } ed = low; vec.push_back(st); vec.push_back(ed); } else { vec.push_back(-1); vec.push_back(-1); } return vec; } };

74.搜索二维矩阵
思路解析：
单纯的二分查找，使用模板一、模板二都可以。关键在于二维矩阵下标的表示。

class Solution { public: bool searchMatrix(vector>& matrix, int target) { if(matrix.size() == 0 || matrix[0].size() == 0) return false; int n = matrix.size(); int m = matrix[0].size(); int l = 0 ,r = n * m - 1; while(l < r){ int mid = l + r >> 1; if(matrix[mid/m][mid%m] >= target) r = mid; else l = mid + 1; } if(matrix[r/m][r%m] == target) return true; return false; } };

153.寻找旋转排序数组中的最小值
思路解析：
由题意知，旋转数组如图所示，要找最小值等价于00001111找第一个1。我们只要把判断条件设置为小于等于数组最后一个值，此时左边由图知是大于数组最后一个值的，设置为0，右边设置为1。

文章图片

class Solution { public: int findMin(vector& nums) { int len = nums.size(); int l = 0, r = len - 1; while (l < r) { int mid = l + r >> 1; if (nums[mid] <= nums.back()) r = mid; else l = mid + 1; } return nums[l]; } };

33.搜索选择排序数组
思路解析：
这道题是上一题的进阶版，我们可以按照上一题的思路，先通过二分查找找到旋转数组的最小值。然后对数组最后一个数与目标数进行比较，缩小范围。再进行一次二分查找。

class Solution { public: int search(vector& nums, int target) { int len = nums.size(); if (len == 0) return -1; int l = 0, r = len - 1; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] <= nums.back()) r = mid; else l = mid + 1; } if (target <= nums.back()) r = len - 1; else l = 0, r--; while (l < r) { int mid = (l + r) >> 1; if (nums[mid] >= target) r = mid; else l = mid + 1; } return nums[l] == target ? l : -1; } };

278.第一个错误的版本
思路解析：
这个一眼就能看出是00001111查找第一个1的模型，套模板就可以。

// The API isBadVersion is defined for you. // bool isBadVersion(int version); class Solution { public: int firstBadVersion(int n) { int l = 1, r = n; while (l < r) { int mid = l + (r - l >> 1); if (isBadVersion(mid)) r = mid; else l = mid + 1; } return l; } };

5.总结上面的题目也仅仅是刷一下二分查找的熟练度，下次分享会总结下【二分答案】的专题，那个面试可能问的比较多。
原文地址