极客算法

算法 - 二分查找BS

2020-04-26

二分思想

Binary Search是在排序”数组”中查找指定(Any/First/Last/Closest/Range)元素的一种快速搜索算法。

如下图所示:

查找数字7

  1. 将数组一分为二,中间的元素14与7比较,由于7 < 14, 目标在左边的一半
  2. 将剩余部分一分为二,中间元素6与7比较,由于6 < 7, 目标在右边的一半
  3. 沿着图中箭头,不断的把问题缩小一半,直到找到目标

binary_search_with_sorted_array

递归思想

二分算法也是递归思想的一种,但这并不意味着二分一定要用递归来实现。

递归过程:

  1. 二分搜索,将原问题分为左右两个子问题,中间值与目标对比,抛弃一半不可能的,将问题规模缩小一半
  2. 重复步骤1,直到找到目标(或者未找到目标)

时间复杂度分析

二分查找相当于通过O(1)的执行时间(大小比较操作),把问题缩小一半

# T(N)表示一个问题,所需要的执行时间

T(N) = T(N/2) + O(1)
     = (T(N/4) + O(1)) + O(1)
     = ((T(N/8) + O(1)) + O(1)) + O(1)
     ...
     = T(1) + logN * O(1)
     = O(logN)

那通过O(N)的执行时间,把问题缩小一半呢?

倍增思想

一个无穷大的排序数组Arr,要求寻找目标T,但是内存只能读一部分,该怎么解决呢?要求时间复杂度O(LogT)

  1. 如下,首先分别检测第2^K(K>=0)个, 直到找第2^(k-1)个 <= T <= 第2^k
  2. 然后有了上下边界,就可以正常二分了
 第1个    第2个   第4个 
Arr[0], Arr[1], Arr[3], ... Arr[2^(K-1) - 1], Arr[2^K -1]... 

类似的倍增的思想:

  1. 指数退避(Exponential backoff): 爬虫访问
  2. 数组动态扩容策略: vector(C++), ArrayList(Java)

有哪些痛点

  1. 代码死循环,边界条件如何判断
  2. 数据溢出,index有溢出的可能
  3. 丢掉错误的一半,从而错过正确答案
  4. 看不出来,能用二分思想解决

标准化

标准化主要解决1-2条痛点,3-4只能多练习来解决

注意,start=0, end=1. mid=(start + end) // 2, 这里mid=0,也就是说,这个表达式的结果是偏左的

python中引入了新的运算符//, 而原来的/的会保留小数点

正整数情况下和其他语言一样截断,但是负数就会有差异:

mid = (start + end) // 2 = floor((start + rihgt) / 2) # (-7 + -6) // 2 = -7, 结果依然偏左 
mid = (start + end) / 2; // (-7 + -6) / 2 = -6, 结果偏右,如果模版不一致,这个可能会导致死循环

无论是python还是cpp建议使用以下两种方式, 它们可以有效处理正数负数,结果都偏左

mid = (start + end) >> 1
mid = start + (end - start) / 2 # 可以防止溢出

left + 1 < right

不用考虑mid是+1还是-1,只是结果需要额外判断边界

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        if (nums[start] == target ) { // 额外判断
            return start;
        } else if (nums[end] == target) {
            return end;
        } else {
            return -1;
        }
    }
};
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = -1;
        int end = nums.size(); // 左开右开 (start, end)

        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] < target) {
                start = mid;
            } else {
                end = mid;
            }
        }

        return -1;
    }
};

left < right

终止条件left==right, 因为中值偏左, 所以mid = left + 1, 比较简洁, 个人喜欢这个

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;

        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        if (nums[start] == target) { // 额外判断
            return start;
        } else {
            return -1;
        }
    }
};
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size();  // 左闭右开 [start, end)

        while (start < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return -1;
    }
};

left <= right

终止条件是left > right, 结合上一条, right = mid - 1也要让一步, 比较简洁

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start = 0;
        int end = nums.size() - 1;  // 闭区间[start, end]

        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            }

            if (nums[mid] < target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }

        return -1;
    }
};

额外技巧

  1. 拿到一道算法题,除了认真审题,理解要求,要尽快确认属于哪类算法
  2. 优化一个暴力破解为O(N)的算法,那基本上就只能和二分相关了
  3. 问题答案的个数,是该问题算法复杂度的下限
  4. 如果数组中,每个元素都发生了改变,那至少需要O(N)的时间复杂度
  5. 如何恢复[4,5,6,1,2,3]到[1,2,3,4,5,6]三步翻转法, 中间两步:[6,5,4,1,2,3]=>[6,5,4,3,2,1]

-End-


评论

内容:
其他: