再看二分查找

平衡版

1
2
3
4
5
6
7
8
9
10
11
12
public static int binarySearchBalance(int[] a, int target) {
    int i = 0, j = a.length;
    while (1 < j - i) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m;
        } else {
            i = m;
        }
    }
    return (a[i] == target) ? i : -1;
}

思想：

  1. 左闭右开的区间，ii 指向的可能是目标，而 jj 指向的不是目标
  2. 不奢望循环内通过 mm 找出目标, 缩小区间直至剩 1 个, 剩下的这个可能就是要找的（通过 ii）
    • j−i>1j - i > 1 的含义是，在范围内待比较的元素个数 > 1
  3. 改变 ii 边界时，它指向的可能是目标，因此不能 m+1m+1
  4. 循环内的平均比较次数减少了
  5. 时间复杂度 Θ(log(n))\Theta(log(n))

Java 版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private static int binarySearch0(long[] a, int fromIndex, int toIndex,
                                     long key) {
    int low = fromIndex;
    int high = toIndex - 1;

    while (low <= high) {
        int mid = (low + high) >>> 1;
        long midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}
  • 例如 [1,3,5,6][1,3,5,6] 要插入 22 那么就是找到一个位置，这个位置左侧元素都比它小
    • 等循环结束，若没找到，low 左侧元素肯定都比 target 小，因此 low 即插入点
  • 插入点取负是为了与找到情况区分
  • -1 是为了把索引 0 位置的插入点与找到的情况进行区分

Leftmost

有时我们希望返回的是最左侧的重复元素，如果用 Basic 二分查找

  • 对于数组 [1,2,3,4,4,5,6,7][1, 2, 3, 4, 4, 5, 6, 7]，查找元素4，结果是索引3

  • 对于数组 [1,2,4,4,4,5,6,7][1, 2, 4, 4, 4, 5, 6, 7]，查找元素4，结果也是索引3，并不是最左侧的元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int binarySearchLeftmost1(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            candidate = m; // 记录候选位置
            j = m - 1;     // 继续向左
        }
    }
    return candidate;
}

Rightmost

如果希望返回的是最右侧元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int binarySearchRightmost1(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            candidate = m; // 记录候选位置
            i = m + 1;	   // 继续向右
        }
    }
    return candidate;
}

应用

对于 Leftmost 与 Rightmost，可以返回一个比 -1 更有用的值

Leftmost 改为

1
2
3
4
5
6
7
8
9
10
11
12
public static int binarySearchLeftmost(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target <= a[m]) {
            j = m - 1;
        } else {
            i = m + 1;
        }
    }
    return i; 
}
  • leftmost 返回值的另一层含义：<target\lt target 的元素个数
  • 小于等于中间值，都要向左找

Rightmost 改为

1
2
3
4
5
6
7
8
9
10
11
12
public static int binarySearchRightmost(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else {
            i = m + 1;
        }
    }
    return i - 1;
}
  • 大于等于中间值，都要向右找

几个名词

image-20221125174155058

范围查询：

  • 查询 x<4x \lt 4，0..leftmost(4)−10 .. leftmost(4) - 1
  • 查询 x≤4x \leq 4，0..rightmost(4)0 .. rightmost(4)
  • 查询 4<x4 \lt x，$rightmost(4) + 1 … \infty $
  • 查询 4≤x4 \leq x， leftmost(4)..∞leftmost(4) .. \infty
  • 查询 4≤x≤74 \leq x \leq 7，leftmost(4)..rightmost(7)leftmost(4) .. rightmost(7)
  • 查询 4<x<74 \lt x \lt 7，rightmost(4)+1..leftmost(7)−1rightmost(4)+1 .. leftmost(7)-1

求排名：leftmost(target)+1leftmost(target) + 1

  • targettarget 可以不存在，如：leftmost(5)+1=6leftmost(5)+1 = 6
  • targettarget 也可以存在，如：leftmost(4)+1=3leftmost(4)+1 = 3

求前任（predecessor）：leftmost(target)−1leftmost(target) - 1

  • leftmost(3)−1=1leftmost(3) - 1 = 1，前任 a1=2a_1 = 2
  • leftmost(4)−1=1leftmost(4) - 1 = 1，前任 a1=2a_1 = 2

求后任（successor）：rightmost(target)+1rightmost(target)+1

  • rightmost(5)+1=5rightmost(5) + 1 = 5，后任 a5=7a_5 = 7
  • rightmost(4)+1=5rightmost(4) + 1 = 5，后任 a5=7a_5 = 7

求最近邻居：

  • 前任和后任距离更近者

习题

时间复杂度估算

用函数 f(n)f(n) 表示算法效率与数据规模的关系，假设每次解决问题需要 1 微秒（10−610^{-6} 秒），进行估算：

  1. 如果 f(n)=n2f(n) = n^2 那么 1 秒能解决多少次问题？1 天呢？
  2. 如果 f(n)=log2(n)f(n) = log_2(n) 那么 1 秒能解决多少次问题？1 天呢？
  3. 如果 f(n)=n!f(n) = n! 那么 1 秒能解决多少次问题？1 天呢？

参考解答

  1. 1秒 106=1000\sqrt{10^6} = 1000 次，1 天 106∗3600∗24≈293938\sqrt{10^6 * 3600 * 24} \approx 293938 次
  2. 1秒 $2^{1,000,000} $ 次，一天 286,400,000,0002^{86,400,000,000}
  3. 推算如下
    • 10!=3,628,80010! = 3,628,800 1秒能解决 1,000,0001,000,000 次，因此次数为 9 次
    • 14!=87,178,291,20014!=87,178,291,200，一天能解决 86,400,000,00086,400,000,000 次，因此次数为 13 次

耗时估算

一台机器对200个单词进行排序花了200秒(使用冒泡排序)，那么花费800秒，大概可以对多少个单词进行排序

a. 400

b. 600

c. 800

d. 1600

答案

  • a

解释

  • 冒泡排序时间复杂度是 O(N2)O(N^2)
  • 时间增长 4 倍，而因此能处理的数据量是原来的 4=2\sqrt{4} = 2 倍

E01. 二分查找-Leetcode 704

要点：减而治之，可以用递归或非递归实现

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1

例如

1
2
3
4
5
6
7
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
    
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

参考答案：略，可以用讲过的任意一种二分求解

E02. 搜索插入位置-Leetcode 35

要点：理解谁代表插入位置

给定一个排序数组和一个目标值

  • 在数组中找到目标值，并返回其索引
  • 如果目标值不存在于数组中，返回它将会被按顺序插入的位置

例如

1
2
3
4
5
6
7
8
输入: nums = [1,3,5,6], target = 5
输出: 2

输入: nums = [1,3,5,6], target = 2
输出: 1

输入: nums = [1,3,5,6], target = 7
输出: 4

参考答案1：用二分查找基础版代码改写，基础版中，找到返回 m，没找到 i 代表插入点，因此有

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int searchInsert(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            return m;
        }
    }
    return i; // 原始 return -1
}

参考答案2：用二分查找平衡版改写，平衡版中

  • 如果 target == a[i] 返回 i 表示找到
  • 如果 target < a[i]，例如 target = 2，a[i] = 3，这时就应该在 i 位置插入 2
  • 如果 a[i] < target，例如 a[i] = 3，target = 4，这时就应该在 i+1 位置插入 4
1
2
3
4
5
6
7
8
9
10
11
12
13
public static int searchInsert(int[] a, int target) {
    int i = 0, j = a.length;
    while (1 < j - i) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m;
        } else {
            i = m;
        }
    }
    return (target <= a[i]) ? i : i + 1;
    // 原始 (target == a[i]) ? i : -1;
}

参考答案3：用 leftmost 版本解，返回值即为插入位置（并能处理元素重复的情况）

1
2
3
4
5
6
7
8
9
10
11
12
public int searchInsert(int[] a, int target) {
    int i = 0, j = a.length - 1;
    while(i <= j) {
        int m = (i + j) >>> 1;
        if(target <= a[m]) {
            j = m - 1;
        } else {
            i = m + 1;
        } 
    }
    return i;
}

E03. 搜索开始结束位置-Leetcode 34

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

例如

1
2
3
4
5
6
7
8
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

输入：nums = [], target = 0
输出：[-1,-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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public static int left(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            candidate = m;
            j = m - 1;
        }
    }
    return candidate;
}

public static int right(int[] a, int target) {
    int i = 0, j = a.length - 1;
    int candidate = -1;
    while (i <= j) {
        int m = (i + j) >>> 1;
        if (target < a[m]) {
            j = m - 1;
        } else if (a[m] < target) {
            i = m + 1;
        } else {
            candidate = m;
            i = m + 1;
        }
    }
    return candidate;
}

public static int[] searchRange(int[] nums, int target) {
    int x = left(nums, target);
    if(x == -1) {
        return new int[] {-1, -1};
    } else {
        return new int[] {x, right(nums, target)};
    }
}
初识算法 基础数据结构-数组