专题三_二分_二分查找

一：题目

解释：在一个升序数组中找一个值，存在则返回下标

二：算法

①：暴力

从头到尾遍历查找，时间复杂度为O(N)

②：二分

不断的取居中的元素去查找，时间复杂度O(logN)，O(logN)是及其优秀的速度，2³² 也就是42亿多，O(logN)只需32次就能得到结果！而O(N)需要42 亿次！

Q：为什么二分一定对？

A：本质就是省去了无效的暴力，所以肯定正确

③：二分思想

二分板块的第一道题十分简单，但是重点是我们要理解二分的思想！

1：适用二分的题目不一定是有序的，只要你能根据某个条件，让数组具有二段性即可！比如此题中大于target和小于target的元素，就让数组具有了二段性，而在后面的二分类型的题目中，我们不可能这么简单的让其具有二段性，往往需要根据题目去写出一个条件，让数组具有二段性，从而使用二分算法。更有题目，我们会让数组以不同条件，具有不同的二段性质！

2：求居中下标，禁止直接 (left + right) / 2，因为left + right存在超出int范围的风险，导致取的下标不对！应该 left + (right - left) / 2！才是安全的！

3： 求中点的写法，还有一种是 left+(right-left+1)/2，其和 left+(right-left)/2的区别为，奇数个元素无区别，但是偶数个元素 left+(right-left)/2取到前面个元素， left+(right-left+1)/2取到后面个元素，在有些题目，两种写法一致，比如此题，但是有些题目，只能使用其中的某一种才是对的！！

4：所以中点表达式有两种：left+(right-left+1)/2 和 left+(right-left)/2，根据题目而定！

三：代码

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