代码随想录-02二分查找-704二分查找

• 前言
• • 1. 判断是否使用二分查找的3个前提条件
  • 2. 二分查找算法思路：
  • 3. 算法实现
  • 4. 算法分析
  • 5. 算法的坑
• 同类题型

在本科毕设结束后，开始刷“代码随想录”，每天一节。总结笔记均会放在“算法刷题-代码随想录”该专栏下，以下为原文的链接。
二分查找卡尔题解

当题目中包含数据结构为“数组”(比如链表就不可以使用二分查找，因为二分查找只能内存地址连续的数据结构中进行)，并且该“数组为有序数组”以及**“数组中无重复元素”**这三个前提条件，很有可能可以使用“二分查找”。

思路：

• 1.如果待查列表不为空，将他的中间元素与目标元素进行比较，相等则返回下标并结束；
• 2.如果不相等，则比较目标元素与中间元素的大小，
• 3.若目标元素大于中间元素，则把原序列以中间元素开始的右半部分当做新的序列，在新序列中继续查找该目标元素，
• 4.若目标元素小于中间元素，则把原序列以中间元素结尾的左半部分当做新的序列，在新序列中继续查找该目标元素，
• 5.再在新序列中共重复第一步的操作。
  优点：时间复杂度为Log(n),比普通查找快。
  缺点：如下
• 要求数据结构在内存中连续存储（如：数组），并且有序（升序、降序均可）且不重复。
• 数据结构插入删除困难。
  详情链接

• 区间：通过两个int类型（left、right）变量充当左右指针的值，来规定区间范围，区间边界都闭合，一个int类型(mid)变量充当中间值的下标。
  区间的大小应该大于等于1，也就是说左指针应该不大于右指针，即left <= right。
  若区间范围小于1，还未找到，则说明该区间不含有目标值。
• 通过循环实现判定目标值和中间元素值大小的比较。
  代码：

#include
#include
using namespace std;
int binarySearch(vector nums,int target){
	int left = 0,right = nums.size() - 1,mid;
	while(left <= right){
		mid = left + (right - left) / 2;//right肯定大于left,故right - left不会导致溢出Integer的最大值;并且整个表达式等同于 (right + left)/ 2,可以自己试着将两者转换
		if(target < nums[mid]){
			right = mid- 1;
		}else if(target > nums[mid]){
			left = mid + 1;
		}else{
			return mid;
		}
	}
	return -1;
}

n为数组长度
时间复杂度：O(logn)
空间复杂度:O(1),只增加了left、right、mid，这3个变量。（算法中的nums虽然空间大小是n,但是在计算空间复杂度时只计算额外增加的空间大小）

• 中间值mid最好写成mid = l + (r - l) / 2，而不是容易想到的mid= (l + r) / 2;
  因为l + r的值可能超过int的最大范围而造成溢出。
  为什么二分法不建议使用 (right + left) / 2？相关链接

• 什么叫做“循环不变量”
  在每次循环中都满足的条件，在写循环时要清楚循环中的循环不变量是什么。
  举例
  二分法中的循环不变量是，每次循环时查找target的额区间的区间边界是开还是闭

• C++中位右移一位（>> 1），在符号的运算中相当于除以2，且右移一位的速度快于/2的速度
  C++位右移是什么
  轻松理解 left + ((right -left) ＞＞ 1)

35. 搜索插入位置