一、题目
1、原题链接
704. 二分查找
2、题目描述
二、解题报告
1、思路分析
二分查找有一般有两种写法，主要思想是利用搜索区间的定义来确定代码条件：
[left,right]（左闭右闭）
如果将区间定义为左闭右闭，则意味着left和right的值都可以取到，而且left和right的值可以相等。所以：
初始left=0、right=nums.size()-1。
循环条件需要设置为left<=right
当nums[mid]>target时，更新right=mid-1。（因为根据区间定义，此时如果使right=mid，区间可以取到mid，而已知mid不满足条件，故应将区间缩小为[left,mid-1]）
当nums[mid]<target时，更新为left=mid+1。（因为根据区间定义，此时如果使left=mid，区间可以取到mid，而已知mid不满足条件，故应将区间缩小为[mid+1,right]）
当nums[mid]==target时，返回mid。
否则，返回-1。
[left,right)（左闭右开）
如果将区间定义为左闭右开，则意味着left的值可以取到，而right的值取不到，而且left和right的值不可以相等。所以：
初始left=0、right=nums.size()。
循环条件需要设置为left<right
当nums[mid]>target时，更新right=mid。（因为根据区间定义，此时如果使right=mid-1，区间取不到mid-1，会使搜索区间丢失mid-1，故应将区间缩小为[left,mid)）
当nums[mid]<target时，更新left=mid+1。（因为根据区间定义，此时如果使left=mid，区间可以取到mid，而已知mid不满足条件，故应将区间缩小为[mid+1,right)）
当nums[mid]==target时，返回mid。
否则，返回-1。
2、时间复杂度
二分查找时间复杂度为O (log n)
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 - left) / 2); //或 //int mid = left + ((right - left) >> 1); int mid = (left + right) / 2; if (nums[mid] > target) right = mid - 1; else if (nums[mid] < target) left = mid + 1; else return mid; } return -1; } };
左闭右开区间定义代码
class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size(); while (left < right) { //防止溢出可以改为： //int mid = left + ((right - left) / 2); //或 //int mid = left + ((right - left) >> 1); int mid = (left + right) / 2; if (nums[mid] > target) right = mid; else if (nums[mid] < target) left = mid + 1; else return mid; } return -1; } };
三、知识风暴
注意mid是下标不是值，与target比较时是用nums[mid]。
防止溢出可以将int mid = (left + right) / 2;改为 int mid = left + ((right - left) / 2);或int mid = left + ((right - left) >> 1);。
数组理论基础
数组下标都是从0开始的
数组在内存空间的地址是连续的
数组中的元素只能覆盖，不能删除。
