leetcode之二分查找

二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时，都应该考虑二分查找。如果集合是无序的，我们可以总是在应用二分查找之前先对其进行排序。

成功的二分查找的 3 个部分

二分查找一般由三个主要部分组成：

预处理 —— 如果集合未排序，则进行排序。二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。后处理 —— 在剩余空间中确定可行的候选者。

模板

int binarySearch(int[] nums, int target) { int left = 0, right = ...; //right的初始化于搜索区间的类型决定,为了不越界 while(...) //终止条件,决定这搜索区间是左闭右开还是左闭右闭 { int mid =left+(right-left)/2; //可以防止溢出 if (nums[mid] == target) { ... //数据更新 } else if (nums[mid]< target) { left = ... //left更新,依据是下一步去哪个区间进行搜索 } else if (nums[mid]> target) { right = ... //right更新,依据是下一步去哪个区间进行搜索 } } return ...; } 初始条件：left = 0, right = length-1 终止：left > right 向左查找：right = mid-1 向右查找：left = mid+1

---

关键

分析二分查找的一个技巧是:不要出现 else,而是把所有情况用else if写清楚,这样可以清楚地展现所有细节。本文都会使用else if,旨在讲清楚,读者理解后可自行简化。其中…标记的部分,就是可能出现细节问题的地方,当你⻅到一个二分查找的代码时,首先注意这几个地方。后文用实例分析这些地方能有什么样的变化。 另外声明一下,计算 mid 时需要防止溢出,代码中 left+(right-left)/2 就和(left+right)/2 的结果相同,但是有效防止了left和right太大直接相加导致溢出。

一定要明白,我维持查找的窗口是怎么样的,我查找完以后里面的细节是怎么样的(也就是怎么缩小窗口)

例题:

我们正在玩一个猜数字游戏。 游戏规则如下： 我从 1 到 n 选择一个数字。 你需要猜我选择了哪个数字。 每次你猜错了，我会告诉你这个数字是大了还是小了。 你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：

-1 : 我的数字比较小 1 : 我的数字比较大 0 : 恭喜！你猜对了！

示例 :

输入: n = 10, pick = 6 输出: 6 class Solution { public: int guessNumber(int n) { int L=1,R=n; while(L<=R)//维持一个[left,right],这也决定了right的初始化 { int mid=L+(R-L)/2;//L+R会溢出,超出int cout<<mid; int tar=guess(mid); if(tar==0) return mid; else if(tar==1) L=mid+1;//加加减减是根据下一步去那个区间寻找决定的; else if(tar==-1) R=mid-1; } return -1; } };

示例:

寻找右边界

给你一个大小为 m * n 的方阵 mat，方阵由若干军人和平民组成，分别用 1 和 0 表示。 请你返回方阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。 如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。 军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。 输入：mat = [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]], k = 3 输出：[2,0,3] 解释： 每行中的军人数目： 行 0 -> 2 行 1 -> 4 行 2 -> 1 行 3 -> 2 行 4 -> 5 从最弱到最强对这些行排序后得到 [2,0,3,1,4] class Solution { public: vector<int> kWeakestRows(vector<vector<int>>& mat, int k) { //思路,查找右边界,找出每一行,军人的位置. //然后把位置压入一个vector,再利用sort() vector<int> res(3,0); int row=mat.size(); int col=mat[0].size(); map<int,int> tmpres; for(int i=0;i<row;i++) { int left=0,right=col-1; while(left<=right)//这里维持的查找区间是[left,right] { int mid=left+(right-left)/2; if(mat[i][mid]==1)//找到后数据更新 { left=mid+1; } else if(mat[i][mid]!=1)//未找到数据更新 { right=mid-1; } } //返回 tmpres[right+1]=i; } for(auto &t:tmpres) { cout<<t.first<<endl; } return res; } };