【21天算法挑战赛】查找算法——二分查找

​​​💬💬作者有话想说：

💟作者简介：我目前是一个在校学生，想通过自己的学习努力让自己的技术、知识都慢慢提升，希望我们一起学习呀~💜💜💜
 
☂️兴趣领域：目前偏向于前端学习 💜💜💜
 
🎬> 活动地址：CSDN21天学习挑战赛
 
💜有话想说：写博客、记笔记并不是一种自我感动，把学到的东西记在脑子里才是最重要的，在这个过程中，不要浮躁，希望我们都可以越来越优秀！💜💜💜
 
🪀语言说明：代码实现我会用Python/C++~

一、二分查找

1.1.二分查找简介

• 在列表中查找一个元素的位置时，
• 如果列表是无序的，我们只能用穷举法一个一个顺序查找。
• 但如果列表是有序的，就可以用二分查找(折半查找、二分搜索)算法。
• 二分查找是一种效率极高的算法！边界问题是二分的关键！

1.2.二分查找思路

查找前提：二分查找算法必须是有序的！

思路💡💡：

1. 首先确定整个查找区间的中间位置 mid = strat+(end-strat)/2
2. 用待查关键字key值与中间位置的关键字值进行比较；若相等，则查找成功。若大于，则在后 (右）半个区域继续进行折半查找。若小于，则在前（左）半个区域继续进行折半查找
3. 对确定的缩小区域再按折半公式，重复上述步骤。

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;
    }
};



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

1.6.优缺点

优点：

比较次数少，查找速度快，平均性能好；

缺点：

要求待查表为有序表，且插入删除困难。

附：二分查找mid值溢出问题

为我之前写的一篇博客，现在整合到一起了： 二分查找mid值溢出问题
​
二分查找时，我们往往会见到以下三种方法来求mid中间值

1. 正常思路

mid = (left + right) / 2;
1

2. 防溢出写法

mid = left + (right - left)/2;
1

3. 位运算 也是防溢出 无符号位元素符的优先级较低，所以括起来

mid = left + ((right - left)>>2);
1

那么为什么第一种方法会溢出呢？

我之前学二分的时候，当时是两种写法都有人用，但是第二种方法说是可以防止溢出，我当时也没有在意，今天早上醒来打开手机看见二分，突然想到这个问题了，所以想记录一下这个问题；

1. 第一种方法可能会溢出原因

• 一般我们都是定义左边界（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
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 而写成第二种方法 mid = left +（right -left)/2 的就会相对安全，（right - left）使用减法不会超出最大的整型范畴；给第二种方法通分一下就和第一种方法的式子一样。

• 写成第三种方法 mid = left +((rightt-left)>>2) 位运算，（效率是挺高的，就是嘛，不易懂hh）>>表示右位移运算符，把操作数的二进制码右位移指定位数，左边空出来的位以原来的符号位填充。原来是负数就填充1，原来是正数就填充0。符号位不变。

持续更新中，fighting！💜💜💜

​

​