二分查找 | 二分模板 | 二分题目解析

1.二分查找

二分查找的一个前提就是要保证数组是有序的（不准确）！利用二段性！
1.朴素二分模板
朴素二分法的查找中间的值和目标值比较

while(left <= right)	// 注意是要： <=
{int mid = left + (right -left) / 2;	// 避免溢出if(条件){left = mid + 1;}else if(条件){right = mid -1;}else{return 结果;}
}

练习题目：
leetcode704. 二分查找
leetcode33 搜索旋转排序数组

1、nums[mid] >= nums[left] （以左端点为参考点）说明mid 落在的AB 端 否则落在了CD段
2、当mid落在AB段中，当 target >= nums[left] （以左端点为参考点）&& target < nums[mid] 说明了right = mid -1。否则就是落在了[mid + 1,B]段，移动left = mid + 1;
3、当mid落在了CD段中，当 target <= nums[right]（以右端点为参考点） && target > nums[mid] 说明移动left = mid -1。否则right = mid - 1

2.查找左右边界的二分模板
这个模板也可以解决第一个模板的题，他比较万能。

左边界模板
while(left < right)
{int mid = left + (right - left) / 2;if(条件) left = mid + 1;else right = mid;
}
右边界模板
while(left < right)
{int mid = left + (right - left + 1) / 2;if(条件) left = mid;else right = mid -1;
}

leetcode162 寻找峰值
峰值大于相邻的左和右，mid可以是落在任何位置。这里用到了查找右边界的二分模板
1、当nums[mid] > nums[mid -1] 说明是在递增left 往右移动。left = mid （这里只判断了mid 的左边，mid可能就是峰值）
2、else （即：nums[mid] < nums[mid - 1] ） 说明在递减区域如BC。right = mid - 1。

参考代码：

int findPeakElement(vector<int>& nums) 
{if(nums.size() == 1) return 0;if(nums.size() < 3) return nums[1] > nums[0] ? 1 : 0;int left = 0,right = nums.size() -1;while(left < right){int mid = left + (right - left+ 1) / 2;if(nums[mid] > nums[mid -1]) {left = mid;}else{right = mid - 1;}}return left;
}

leetcode35 搜索插入位置
找到数组中的元素，如过找不到，返回target插入的下标索引。

如上图数组的左边部分的元素是 <target，右边>= target
1、nums[mid] < target 说明 left = mid + 1
2、nums[mid] >= target 说明 right = mid。有可能mid就是要找的元素
3、当循环结束后（left == right）说明数组中的值没有对应的target。当nums[left] < target。说明target要插入在left后面返回 left + 1 否则返回 left。
参考代码：

int searchInsert(vector<int>& nums, int target) 
{int left = 0,right = nums.size() -1;while(left < right){int mid = left +  (right - left) / 2;if(nums[mid] == target) return mid;if(nums[mid] < target){left = mid + 1;}else{right = mid;}}return nums[left] < target ? left +1 : left;
}

leetcode34、在排序数组中查找元素的第一个和最后一个位置
找到最左边的（第一个位置）：

1、当nums[mid] < target则left = mid + 1
2、当nums[mid] >= target 则right = mid （mid可能就是最左边的target）

找到最右边的（最后一个位置）：

1、当nums[mid] > target 则right = mid - 1
2、当nums[mid] <= target 则 left = mid

参考代码：

vector<int> searchRange(vector<int>& nums, int target) 
{if(nums.size() == 0) return {-1,-1};vector<int> ret;int left = 0, right = nums.size() -1;while(left < right){int mid = left + (right -left) / 2;if(nums[mid] < target){left = mid + 1;}else{right = mid;}}nums[left] == target ? ret.push_back(left) : ret.push_back(-1);left = 0;   // 可以的不用重置right = nums.size() -1;while(left < right){int mid = left + (right - left + 1) / 2;if(nums[mid] > target){right = mid - 1;}else{left = mid;}}nums[right] == target ? ret.push_back(left): ret.push_back(-1);return ret;
}

leetcode153. 寻找旋转排序数组中的最小值

1、求最小值，一定是在CD段的，准确说是端点C！但是mid可能会AB段，当落到AB就要移动left，什么条件满足移动呢（参考点是什么）
2、当 nums[mid] > nums[right] 时 left = mid - 1
3、当 nums[mid] <= nums[right] 时 right = mid

int findMin(vector<int>& nums) 
{int left = 0,right = nums.size() -1;while(left < right){int mid = left + (right - left) / 2;if(nums[mid] > nums[right]){left = mid + 1;}else{right = mid;}}return nums[left];
}