一，二分查找
1，题目描述
在一个给定的有序数组中，查找目标值target，返回它的下标。如果不存在，返回-1
2，思路
解法一：暴力枚举，遍历整个数组，直到找到目标值，返回下标。
解法二：利用数组的有序性，使用二分查找算法。使用两个指针left和right来维护要查找的区间，每次使用该区间的中间值与target目标值比较。图示：
3，代码实现
class Solution {
public:int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right){int mid=(left+right)/2;if(nums[mid]>target)right=mid-1;else if(nums[mid]<target)left=mid+1;elsereturn mid;//找到了}return -1;}
};4，总结朴素二分模板
二，在排序数组中查找元素的第一个位置和最后一个位置
1，题目描述
在一个整数数组中找到target目标值第一次出现的位置，和最后出现的位置。
2，思路
解法一：题目中数组是有序的，所以我们可以利用二分查找的二段性思想来解决，所谓二段性，就是通过某种规律可以将数组分成两部分，再通过判断我们可以舍去一部分。从而加快查找。
图示：以查找target第一次出现的位置为例
同理，查找最后一次出现的位置
细节问题：
3，代码实现
class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> v;if (nums.size() == 0)return {-1, -1};// 查找第一次出现的位置int left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}if (nums[left] == target)v.push_back(left);elsev.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;elseleft = mid;}if (nums[left] == target)v.push_back(left);elsev.push_back(-1);return v;}
};
4，总结二分模板
关于求中点位置的操作什么时候需要加1，什么时候不需要。只需看下面的left和right ，如果出现-1，mid就需要加1。否则，不需要加1.
三，x的平方根
1，题目描述
给你一个数x,求它的平方根。
2，思路
解法一：枚举，从1开始计算平方，直到计算到等于x的值，并返回
解法二：二段性，二分查找
3，代码实现
四，山脉数组的峰顶索引
1，题目描述
给你一个山脉数组，数组的值是先上升后下降的，求峰顶值的下标
2，思路
解法一：暴力解法，遍历数组，找到第一次出现，前一个元素大于后一个元素的位置，时间复杂度为O(N)
解法二：二分查找，图示
3，代码实现
class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 0, right = arr.size() - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (arr[mid] > arr[mid - 1])left = mid;elseright = mid - 1;}return left;}
};
