一、二分查找
1.1.二分查找简介
- 在列表中查找一个元素的位置时，
- 如果列表是无序的，我们只能用穷举法一个一个顺序查找。
- 但如果列表是有序的，就可以用二分查找(折半查找、二分搜索)算法。
- 二分查找是一种效率极高的算法！边界问题是二分的关键！
1.2.二分查找思路
查找前提：二分查找算法必须是有序的！
思路💡💡：
首先确定整个查找区间的中间位置 mid = strat+(end-strat)/2
- 用待查关键字key值与中间位置的关键字值进行比较；若相等，则查找成功。若大于，则在后 (右）半个区域继续进行折半查找。若小于，则在前（左）半个区域继续进行折半查找
- 对确定的缩小区域再按折半公式，重复上述步骤。
1.3.时间复杂度
💡💡
- 最坏的情况：假使总共有n个元素，那么二分后每次查找的区间大小就是n，n/2，n/4，…，n/2^k，其中k就是循环的次数。 最坏的情况是K次二分之后,每个区间的大小为1,找到想要的元素 令n/2^k=1，
可得k=log2n,（是以2为底，n的对数），所以时间复杂度可以表示O(logn)
- 最好的情况：一次查到，为O(1)
- 综上，二分查找时间复杂度为O(logn)
1.4.空间复杂度
💡💡
算法的空间复杂度并不是计算实际占用的空间，而是计算整个算法的辅助空间单元的个数.由于辅助空间是常数级别的所以： 空间复杂度是O(1);
1.5.代码实现
写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。个人喜欢左闭右闭即[left, right]，以下代码均为左闭右闭型
区间的定义这就决定了二分法的代码应该如何写，两种都可以，看个人喜好哈
- while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
- if (nums[mid] > target) right 要赋值为 middle - 1，因为 mid 已经搜索过，应该从搜索区间中去除。
C++代码：
// 左闭右闭型
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
// 防止溢出 等同于(left + right)/2
int middle = left + ((right - left) / 2);
if (nums[middle] > target) {
// target 在左区间，所以[left, middle - 1]
right = middle - 1;
} else if (nums[middle] < target) {
// target 在右区间，所以[middle + 1, right]
left = middle + 1;
} else { // nums[middle] == target
// 数组中找到目标值，直接返回下标
return middle;
}
}
// 未找到目标值
return -1;
}
};
Python代码：
# 左闭右闭型
from typing import List
# 分别找到正确的左右边界
class Solution:
# 寻找左边界
def getLeftBorder(self, nums, target):
left = 0
right = len(nums) - 1
leftBoder = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] >= target:
right = mid - 1
else:
left = mid + 1
leftBoder = left if nums[left] == target else -1
return leftBoder
# 寻找右边界
def getRightBorder(self, nums, target):
left = 0
right = len(nums) - 1
rightBorder = -1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
rightBorder = right if nums[right] == target else -1
return rightBorder
def searchRange(self, nums: List[int], target: int) -> List[int]:
result = [-1, -1]
n = len(nums)
# 分类情况
if n == 0:
return result
if n == 1:
if nums[0] == target:
result = [0, 0]
return result
if target < nums[0] or target > nums[-1]:
return result
# 找到左右边界索引
LeftBorder = self.getLeftBorder(nums, target)
rightBoder = self.getRightBorder(nums, target)
return [LeftBorder, rightBoder]
1.6.优缺点
优点：
比较次数少，查找速度快，平均性能好；
缺点：
要求待查表为有序表，且插入删除困难。
二分查找时，我们往往会见到以下三种方法来求mid中间值
- 正常思路
mid = (left + right) / 2;- 防溢出写法
mid = left + (right - left)/2;- 位运算 也是防溢出 无符号位元素符的优先级较低，所以括起来
mid = left + ((right - left)>>2);那么为什么第一种方法会溢出呢？
我之前学二分的时候，当时是两种写法都有人用，但是第二种方法说是可以防止溢出，我当时也没有在意，今天早上醒来打开手机看见二分，突然想到这个问题了，所以想记录一下这个问题；
- 第一种方法可能会溢出原因
- 一般我们都是定义左边界（left）和右边界（right）都使用 int 类型，如果 left 和 right 足够大，mid = (left + right)/2，可能会由于 left+right 导致 int 数据类型越界。
- int占用4字节32比特时的取值范围为 -2147483648～2147483647 假设left right 为1073741824
- 加在一起 left+right = 2147483648 超过了int的最大范围 此时就溢出了
- 如果超出int的最大范围 那么结果变成负数，（原本我不太理解为什么超出范围会变成负数，在网上查找资料了解到：
十进制数字存储在计算机时要转换为二进制。数字在累加的时候会不断进位，超过最大范围时符号位就变成了1，1表示的是负数，计算机就理解成这是个负数了（为原码，补码、反码部分的知识））
如下面这个例子
#include<iostream>
using namespace std;
int main()
{
int left = 1073741824;
int right = 1073741824;
int result1 = (left + right) / 2;
int result2 = left + (right - right) / 2;
cout << "result1：" << result1 << endl;
cout << "result2：" << result2 << endl;
system("pause");
return 0;
}
//运行结果
result1：-1073741824
result2：1073741824- 而写成第二种方法 mid = left +（right -left)/2 的就会相对安全，（right - left）使用减法不会超出最大的整型范畴；给第二种方法通分一下就和第一种方法的式子一样。
- 写成第三种方法 mid = left +((rightt-left)>>2) 位运算，（效率是挺高的，就是嘛，不易懂hh）>>表示右位移运算符，把操作数的二进制码右位移指定位数，左边空出来的位以原来的符号位填充。原来是负数就填充1，原来是正数就填充0。符号位不变。
