二分查找算法合集-1
“ 二分查找作为一种高效率的查找方法，在计算机算法中被广泛使用。本系列归纳了基本的二分查找算法，以及二分查找算法的几种变形，包括：lower bound，upper bound等。同时每种算法在leetcode上给出了对应的习题，希望能够帮助到学习算法的同学。”
01
—
二分查找
问：查找是做什么？
答：这里的查找可以理解为从一组数字中，找出某一个数字是否存在，存在的话在第几个位置。例如：从【1，3，2，4，7，6】这组数字中，查找4是否存在，那么可以得到在第4个位置。
问：二分查找是干什么用的呢？
答：在计算机科学中，二分查找算法也叫折半查找算法或者对数搜索算法。是一种在有序的数组中查找特征元素的算法。这里是一种特殊的情况，要求了数组要有序。在【0，2，3，4，15，16】的这种有序的数组中可以用二分查找，在【1，3，2，4，7，6】这种无序的数组中就不能直接使用二分查找。
问：二分查找有什么好处呢？
答：二分查找可以在对数时间复杂度的得到结果，即时间复杂度为O(log n)。例如：在【0，2，3，4，15，16】中查找4是否存在，不用二分查找，可以把每一个数字判断一次，这样共需要判断4次，如果4在最后一个位置，需要查找6次。序列有多长，最差就需要查找多次。使用二分查找，最多只需要查找3次。这样看还不明显，如果序列长度为1024，那么线性查找最多需要查找1024次，而二分查找最多查找10次，差距就很明显了。
上面三个问题解释清楚了二分查找是什么，和为什么使用二分查找的问题。下面我们具体讲解二分查找算法。
给定一个升序数组A=，并且，给定一个目标值T，下面的算法返回A数组中T的位置。
1. 设置L=0，R=n-12. 如果L > R 那么搜索结束，反回失败。3. 令 m = (L+R) / 24. 如果Am < T, 则L = m + 1，返回步骤25. 若果Am > T, 则R = m - 1 返回步骤26. 如果Am = T, 则返回m
说明一下，在计算机中序列是从第0个数字开始的，所以一个序列的序号是0到n-1。另外，在计算机中对整数的除法是向下取整的，例如5/2=2。
以【0，2，3，4，15，16】，查找目标值4为例，演示一遍二分查找算法。设置L=0表示查找范围的最左边位置，设置R=n-1=6-1=5，表示查找范围的最右边，其中n为序列的长度为6。
取m=（L+R）/ 2 = （0+5）/ 2 = 2，计算机中对整数的除法是向下取整的，因此这里m取2，那么A2=3，即第2个元素的值为3。
此时，A2 = 3 < 4，那么L = m + 1 = 2 + 1 = 3.
重复上述步骤，取m=（L+R）/ 2 = （3+5）/ 2 = 4，A4=15 > 4，那么
R = m - 1 = 5 - 1 = 4。
继续重复上述步骤，取m=（L+R）/ 2 = （3+4）/ 2 = 3，A3=4=4，查找成功，返回3，表示4在序列中的第三个位置。
看到这里二分查找的原理已经讲完了，后面的部分是二分查找在leetcode上相关的习题，读者可以选择感兴趣的部分阅读。
02
—
二分查找习题
本节给出二分查找的8道典型leetcode练习题，不仅仅要理解第一节的二分查找形式，更要理解二分查找的思想。后面的部分：题目一是典型的二分查找算法实现；题目二是二分思想在树中的应用；题目三和题目八是二分查找在计算除法和pow中的应用；题目四、五、六、七是二分查找的简单变形，可以套用题目一的范式，只不是简单的条件修改，请仔细对比体会4-7题，后续的系列介绍upper bound和lower bound也会频繁出现4-7题的范式。
另外一点小技巧，在二分查找中，m的计算方法有两种。
1）m=(l+r)/2
2）m=l+(r-l)/2
下面的题目中两种方式都可以使用，但是在熟悉之后，推荐使用第二种方式。原因是l+r容易导致越界，而第二种写法则避免了越界的问题，更加安全。
如果下列题目有没写清楚的地方，或者还有什么想了解的地方，请私信留言，我会在下一期进行解答。
题目1: leetcode 704题
解题思路就是实现一遍上述算法，这里使用c++实现。
class Solution {public:int search(vector<int>& nums, int target) {int l=0, r=nums.size()-1;while(l <= r) {int m = (l+r)/2;if (nums[m] < target) l = m + 1;else if (nums[m] > target) r = m - 1;else {return m;}}return -1;}};
题目2:leetcode 222题
解法一：深度优先搜索dfs，每个node cnt+1，这里不做展示。时间复杂度为O(n)。
解法二：首先，一个满二叉树节点的数量为2^h-1，其中h为树的高度。那么可以通过求出左子树和右子树的高度，如果高度相等，那么左子树是满二叉树，直接返回左子树的节点数量，递归求右子树的节点数量。如果左边比右边多，那么右边是满二叉树，递归求左子树的节点数量，右子树的节点数量可以直接返回。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/class Solution {public:int countNodes(TreeNode* root) {if(!root) return 0;int l = getHeight(root->left);int r = getHeight(root->right);if (l > r) return 1+countNodes(root->left) + (1 << r) - 1;return 1+(1<<l)-1 + countNodes(root->right);}int getHeight(TreeNode* root) {if(!root) return 0;return 1 + getHeight(root->left);}};
题目3:leetcode 29题
解法一：本题首先可以忽略符号，得到结果之后再给定符号。暴力的解法是直接用被除数不断的减掉除数，当不能减的时候，减了多少次就是最终的答案。
解法二：符号判断同解法一。但是减的时候可以不断判断，是否除数是否大于被除数。如果除数比被除数小，那么可以给除数*2，这样的话，这样的话，减一次，相当于原来减两次。按照这个方式递归下去，直到除数大于被除数。然后依次返回，使用减法完成。
class Solution {public:int divide(int dividend, int divisor) {if(divisor == 0 || (dividend == INT_MIN && divisor==-1)) {return INT_MAX;}if (divisor == 1) return dividend;int sign = 1;if((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {sign = -1;}long long int dividend_new = dividend, divisor_new = divisor;if(dividend < 0) dividend_new = -dividend_new;if(divisor < 0) divisor_new = -divisor_new;int result = divide(dividend_new, divisor_new, 1);return sign == 1 ? result : -result;}int divide(long long int ÷nd, long long int divisor, int x) {if (divisor > dividend) {return 0;}int result = 0;result = divide(dividend, divisor << 1, x << 1);if (divisor > dividend) {return result;}dividend -= divisor;return result + x;}};
题目4:leetcode 157题
解法一：暴力求解，直接按顺序扫一遍数组，得到最小值。
解法二：按照二分查找的思路，如果nums[l] < nums[r]，那么数组为递增的，nums[l]为最小值。如果nums[l] < nums[m]，那么左边为递增序列，从右边查找，l = m + 1即可。如果nums[l] > nums[m]，那么最小值肯定不在右边，从左边查找，r = m即可。
class Solution {public:int findMin(vector<int>& nums) {int l = 0, r = nums.size() - 1;while (l <= r) {if (nums[l] < nums[r]) return nums[l];int m = (l + r) / 2;if (nums[l] < nums[m]) l = m + 1;else {if(l + 1 >= r) return nums[r];else r = m;}}return l;}};
题目5:leetcode 162题
解法：如果没有复杂度要求，直接顺序查找一次就行，找到一个大于左右两边的就返回。要求复杂度为O(logn)，肯定要使用二分查找。当前数字为mid，那么比较mid-1和mid+1的数字，只向大的一遍查找即可。因为大的一边至少会存在一个peak。
class Solution {public:int findPeakElement(vector<int>& nums) {if(nums.size() == 1) return 0;int left=0, right=nums.size();while(left<right) {int mid = left+(right-left)/2;if(mid == 0) {if(nums[0] > nums[1]) return 0;else left=1;} else if(mid == nums.size()-1) {if(nums[nums.size()-1] > nums[nums.size()-2]) return nums.size()-1;else right=nums.size()-1;} else {if(nums[mid] < nums[mid-1]) {right = mid;} else if(nums[mid] < nums[mid+1]) {left = mid+1;} else {return mid;}}}return 0;}};
题目6:leetcode278题
解法：二分查找，如果version(m)是badversion，那么第一个badversion在l到m之间，如果version(m)不是badversion，那么第一个badversion在m+1到n之间。
// The API isBadVersion is defined for you.// bool isBadVersion(int version);class Solution {public:int firstBadVersion(int n) {long long int l = 1, r = n;while(l < r) {int m = (l + r) / 2;if(isBadVersion(m)) r = m;else l = m+1;}return l;}};
题目7:leetcode 275题
解法：还是二分查找的套路，只不过判断条件需要改为n-m，即文章的数量。
class Solution {public:int hIndex(vector<int>& citations) {int n = citations.size();int l = 0, r = n - 1;while (l <= r) {int m = l + (r-l) / 2;if (citations[m] == n-m) return n-m;if (citations[m] > (n-m)) {r = m - 1;}else {l = m+1;}}return n - l;}};
题目8:leetcode 50题
解法：使用二分法的思想递归，例如：2的15次方就等于2^7*2*7*2，递归可得2^7=2^3*2^3*2，继续递归2^3=2^1*2^1*2，最后2^0=1。然后不断递归返回。这样2^7, 2^3, 2^1都只计算了一次，也不需要2*2*2...*2计算15次。当n为负数这样写也成立，half就是每次折半之后的结果，只不过单独的乘法要改成除法。
class Solution {public:double myPow(double x, int n) {if (n == 0) return 1;double half = myPow(x, n / 2);if (n % 2 == 0) return half * half;if (n > 0) return half * half * x;return half * half / x;}};