二分查找算法——二分查找

一.题目描述

704. 二分查找 - 力扣（LeetCode）

二.题目解析

题目非常简单，就是在一个数组里面找目标值即可。

三.算法原理

1.暴力解法

我们直接从头遍历一遍这个数组，同时进行比较。最坏的情况就是找不到目标值。

时间复杂度：O(n)

空间复杂度：O(1)

2.二分查找算法

暴力解法就是每一次判断一个数，舍弃一个数。这样根本没有利用到数组有序的条件。

我们对暴力解法进行优化：我们在区间内随便选一个数，然后进行判断，有三种结果：<target,>target,==target.

如果其小于目标值，说明可以舍弃这个数，而数组是有序（升序）的，当前数的左边区间的所有数一定小于该数，也就一定目标值，所以我们可以一次舍弃到一个区间。

接着在另外一个区间内，再继续随便找一个数， 判断也有三种结果，要么直接找到目标值，要么将区间分为两部分。我们重复这个过程即可。

---

二段性：

我们总结上面的过程可以得出结论，只要数组有”二段性“这样的特点，就可以使用二分查找算法来解决。二段性：可以将数组从某一个分成两部分。

对于分出的两部分来说，我们既可以分为对称的两部分即折半，也可以从3:1的位置分，4:1也可以分。只要分出来的两部分对于中间的点来说有其自己的特性即可。

那么之所以有二分查找，而没有三分、四分查找算法的原因是因为，二分这样的舍弃行为的时间复杂度是很优秀的，比其他的分割方式都要优秀。证明的话需要用数学知识，这里就不再赘述了。

循环的结束条件：

因为区间的值都是未知的，即使最后区间只有一个数->right == left，那个数也是未知的，所以我们也要进行判断，所以循环的结束条件就是left>right.

二分算法的时间复杂度：

当我们查找1次，剩下n/2；2次，剩下n/4；3次，剩下n/8…………当查找x次后，剩余1个。我们对这些进行整理，1->n/2^1、2->n/2^2、3->n/2^3…………x->n/2^x。进行x次之后，剩余1个数，n/2^x = 1，2^x = n，解得，x = log n。

所以二分查找的时间复杂度为O(logN).

空间复杂度：O(1)

四.代码实现

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

# pythonleft,right = 0,len(nums)-1while left<=right:mid = (right-left)//2+leftif nums[mid] > target:right = mid - 1elif nums[mid] < target:left = mid + 1else:return midreturn -1