Python二分查找应用
import bisect
i = bisect.bisect_right
bisect_right：查找大于x的第一个数的位置，如果x比所有都大，位置是len(nums),
Bisect_left: 查找>=x的第一个数的位置，就是最左边的位置。
查找最后一个<=key：besect_right(key), i-1 if i > 0 else None,
查找最后一个<key: besect_left(key), i-1 if i > 0 else None
查找第一个>=key: besect_left(key), i, 可能越界
查找第一个>key: besect_right(key), i, 可能越界
基本二分查找
/**
* 二分查找，找到该值在数组中的下标，否则为-1
*/
static int binarySerach(int[] array, int key) {
int left = 0;
int right = array.length - 1;
// 这里必须是 <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] == key) {
return mid;
}
else if (array[mid] < key) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
return -1;
}
如果题目要求找到则返回索引，没找到则返回本该插入的位置，和二分查找一样，记得返回left,最后插入位置位于right和left之间
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[mid] > target) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return left;
}
};
其实也可以用C++的STL算法代替
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
return lower_bound(nums.begin(), nums.end(), target) - nums.begin();
}
};
二分查找变种
记得array[mid]和key的比较符号，如果有>，就是right=mid-1;否则就是left=mid+1; 
查找第一个与key相等的元素
// 查找第一个相等的元素
static int findFirstEqual(int[] array, int key) {
int left = 0;
int right = array.length - 1;
// 这里必须是 <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] >= key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
if (left < array.length && array[left] == key) {
return left;
}
return -1;
}
查找最后一个与key相等的元素
// 查找最后一个相等的元素
static int findLastEqual(int[] array, int key) {
int left = 0;
int right = array.length - 1;
// 这里必须是 <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] <= key) {
left = mid + 1;
}
else {
right = mid - 1;
}
}
if (right >= 0 && array[right] == key) {
return right;
}
return -1;
}
查找最后一个等于或者小于key的元素
// 查找最后一个等于或者小于key的元素
static int findLastEqualSmaller(int[] array, int key) {
int left = 0;
int right = array.length - 1;
// 这里必须是 <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] > key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return right;
}
查找最后一个小于key的元素
// 查找最后一个小于key的元素
static int findLastSmaller(int[] array, int key) {
int left = 0;
int right = array.length - 1;
// 这里必须是 <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] >= key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return right;
}
查找第一个等于或者大于key的元素
// 查找第一个等于或者大于key的元素
static int findFirstEqualLarger(int[] array, int key) {
int left = 0;
int right = array.length - 1;
// 这里必须是 <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] >= key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return left;
}
查找第一个大于key的元素
// 查找第一个大于key的元素
static int findFirstLarger(int[] array, int key) {
int left = 0;
int right = array.length - 1;
// 这里必须是 <=
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] > key) {
right = mid - 1;
}
else {
left = mid + 1;
}
}
return left;
}
用二分查找法找寻区域
之前我们使用二分查找法时，都是基于数组中的元素各不相同。假如存在重复数据，而数组依然有序，那么我们还是可以用二分查找法判别目标数是否存在。不过，返回的index就只能是随机的重复数据中的某一个。
此时，我们会希望知道有多少个目标数存在。或者说我们希望数组的区域。
结合前面的界限查找，我们只要找到目标数的严格上届和严格下届，那么界限之间（不包括界限）的数据就是目标数的区域了。
在轮转后的有序数组上应用二分查找法
之前我们说过二分法是要应用在有序的数组上，如果是无序的，那么比较和二分就没有意义了。
不过还有一种特殊的数组上也同样可以应用，那就是“轮转后的有序数组（Rotated Sorted Array）”。它是有序数组，取期中某一个数为轴，将其之前的所有数都轮转到数组的末尾所得。比如{7, 11, 13, 17, 2, 3, 5}就是一个轮转后的有序数组。非严格意义上讲，有序数组也属于轮转后的有序数组——我们取首元素作为轴进行轮转。
第一种是无重复的，也就是说左边和右边不会相等
33.Search in Rotated Sorted Array
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
else if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target <= nums[mid]) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
else {
if (nums[mid] < target && target <= nums[r]) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
}
return -1;
}
};
第二种是有重复的，可能nums[l]==nums[r]，这个要注意。
每次两边相等时，进行缩量
if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
l++;
r--;
}
如81.Search in Rotated Sorted Array II
class Solution {
public:
bool search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return true;
}
if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
l++;
r--;
}
else if (nums[l] <= nums[mid]) {
if (nums[l] <= target && target <= nums[mid]) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
else {
if (nums[mid] <= target && target <= nums[r]) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
}
return false;
}
};
有+1/-1的二分查找模板
一般使用while(l<=r)的形式，这样最后结果是l = r+1
但对于需要判断mid和mid+1或者mid-1时就捉襟见肘了，有边界case，比如mid+1>r了这样就不行了。
所以使用新方法，参考
其实就是不管啥问题，都通过while循环把数据区间逼近到[lo, hi]（其中，lo + 1 == hi）两个值，所以出来循环后只要判断一下 lo 和 hi 就行了。
这里lo，hi就是原来的l,r，最终结果是l+1==r, 在此之前取mid时，都不会有mid+1/-1 超过l或者r的情况，就可以放心的进行mid+1和mid-1了，不过此时注意，这时更新l/r就是=mid了，而不是原来的mid+1或者mid-1
int lo = 0, hi = mountainArr.length() - 1;
while (lo + 1 < hi) {
int mid = lo + (hi - lo) / 2;
int midVal = mountainArr.get(mid);
if (midVal > mountainArr.get(mid - 1)) {
lo = mid;
} else {
hi = mid;
}
}
int peakIdx = mountainArr.get(lo) > mountainArr.get(hi)? lo: hi;