少年班的助教课引发的二分查找法变形

Posted on | In

题目

最近少年班的C语言课上老师出了一道题目，题目要求先排序，再给一个元素进行二分查找，最后把该元素key插入到数组中仍然有序。
image
在上机课前思考了一下，假如说元素是往后挪的，如何找出最合适的位置，使得需要挪动的元素个数最小。

  • 对于key元素没有重复的一组数，二分查找出的位置（right指针）就是待插的位置。
  • 但是key这个数有重复的一组数，二分查找出的位置不一定能保证挪动次数最少。应该要找到第一个大于key的数的位置，在这个位置插入key，才能保证挪动次数最少。

分析

这个问题，其实是变形二分法的一种。最开始想法是仍就用基本的二分法，最后在加一for循环，一个个元素比对过去找出最合适的值。可是，这样子又把查找插入位置的时间复杂度提高到了O(n)，能否通过修改二分查找法，直接找出那个位置的。
答案是可以的。开始之前，先看下基本的二分查找法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//基本的二分法
    public int search(int[] arr,int key) {
        int left = 0, right = arr.length-1;
        int mid;
        while (left <= right) {

            mid = left + ((right - left) >> 1);//>> 优先级比+低
            if (arr[mid] == key) return mid;
            else if (arr[mid] > key) right = mid - 1;
            else left = mid + 1;
        }
        
        return -1;
    }

这个代码很简单，要注意while循环里的=不要忘。
首先来看下查完之后，left、right的位置：

  • 查到的话要么l与r在mid等距的两边； 要么left=mid，r=l或r=left+1；
  • 查不到的话right<left,刚好夹在key两侧
    变形的二分查找种类很多，诸如找出第一个与key相等的元素、找出最后一个与key相等的元素……
    改的话要：
    1. 删去if (arr[mid] == key) return mid; 因为mid不一定是合适的位置
    2. 修改 if (arr[mid] > key)的大于符号 因为要对right、 left的位置和基本版不同
    3. 循环结束后要返回查到的位置或返回无结果；

如何改这些，主要是要先分析两步：根据问题要求确定left和right的最终位置（要返回left还是right）、结合题目要求修改比较符号。

以“查找第一个与key相等的元素位置”为例，假如一组数1，2，3，3，4，5，待查的数是3。
第一步： 因为删去了if (arr[mid] == key) return mid; ，所以while循环结束时，肯定是left > right,而且这两个数肯定要是在边界上，如下图所示。这样我们返回left就是answer了。
image
第二步： 那怎么修改比较符号呢，原来if (arr[mid] > key) right = mid - 1;每一轮循环里，只有a[mid]是比key大，right才会变化。现在呢，不仅a[mid]比key大时right要改，当a[mid]等于key时，right也得改，这样它才能挪到元素2那里。因此改为if (arr[mid] >= key) right = mid - 1;

最后针对iii: 因为返回的是left，所以对left做一些限定if (left < n && arr[left] == key) return left;

代码实现

代码把基本的二分查找，以及六种变形情况实现了一下，最重要的地方都有注释

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
public class ExtendeBinarySearch {
    //基本的二分法
    public int search(int[] arr,int key) {
        int left = 0, right = arr.length-1;
        int mid;
        while (left <= right) {

            mid = left + ((right - left) >> 1);//>> 优先级比+低
            if (arr[mid] == key) return mid;
            else if (arr[mid] > key) right = mid - 1;
            else left = mid + 1;
        }
        // 查到的话要么l与r在mid等距的两边 要么left=mid，r=l或r=left+1；
        // 查不到的话right<left,刚好夹在key两侧
        return -1;
    }

    //1. 找出第一个与key相等的元素
    // 1 2R 3L 3 4 返回L
    public int searchFirstEqual(int[] arr,int key) {

        int left = 0, right = arr.length-1;
        int n=arr.length-1;
        int mid;
        while (left <= right) {

            mid = left + ((right - left)>>1);
            //if (arr[mid] == key) return mid;
            if (arr[mid] >= key) right = mid - 1;//结合 图例，等于key之后，R还需要移动
            else left = mid + 1;
        }
        if (left <= n && arr[left] == key) return left;//>= 比 && 高
        return -1;
    }

    // 2. 找出最后一个与key相等的元素
    // 1 2 3 3R 4L 返回R
    public int searchLastEqual(int[] arr,int key) {
        int left = 0, right = arr.length-1;
        int n=arr.length-1;
        int mid;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            //if (arr[mid] == key) return mid;
            if (arr[mid] > key) right = mid - 1;//结合 图例，等于key之后，R还需要移动（即本轮循环不移动R，但是要移动L，下一轮mid重新计算后，R仍然有可能移动
            else left = mid + 1;
        }
        if (right >= 0 && arr[right] == key) return right;
        return -1;
    }

    // 3. 查找第一个等于或者大于Key的元素
    // 1 2R 3L 3 4 返回L
    public int searchFirstEqualorLarger(int[] arr,int key) {
        int left = 0, right = arr.length-1;
        int n=arr.length-1;
        int mid;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            //if (arr[mid] == key) return mid;
            if (arr[mid] >= key) right = mid - 1;//结合 图例，等于key之后，R还需要移动
            else left = mid + 1;
        }
        if (left <= n && arr[left] >= key) return left;
        return -1;
    }

    // 4. 查找第一个大于key的元素
    // 1 2 3 3R 4L 返回L
    public int searchFirstLarger(int[] arr,int key) {
        int left = 0, right = arr.length-1;
        int n=arr.length-1;
        int mid;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            //if (arr[mid] == key) return mid;
            if (arr[mid] > key) right = mid - 1;//结合 图例，等于key之后，R不需要移动
            else left = mid + 1;
        }
        if (left <= n && arr[left] > key) return left;
        return -1;
    }

    // 5. 查找最后一个等于或者小于key的元素
    // 1 2 3 3R 4L 返回R
    public int searchLastEqualorSmaller(int[] arr,int key) {
        int left = 0, right = arr.length-1;
        int mid;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            //if (arr[mid] == key) return mid;
            if (arr[mid] > key) right = mid - 1;//结合 图例，等于key之后，R不需要移动
            else left = mid + 1;
        }
        if (right >= 0 && arr[right] <= key) return right;
        return -1;
    }

    // 6. 查找最后一个小于key的元素
    // 1 2R 3L 3 4 返回R
    public int searchLastSmaller(int[] arr,int key) {
        int left = 0, right = arr.length-1;
        int mid;
        while (left <= right) {
            mid = left + ((right - left) >> 1);
            //if (arr[mid] == key) return mid;
            if (arr[mid] >= key) right = mid - 1;//结合 图例，等于key之后，R还需要移动
            else left = mid + 1;
        }
        if (right >= 0 && arr[right] < key) return right;
        return -1;
    }

}

测试结果

1
2
3
4
5
6
7
8
9
10
int arr[] = new int[] {1,
                2, 2, 5, 5, 5,
                5, 5, 5, 5, 5,
                5, 5, 6, 6, 7};
        System.out.println("First Equal           :"+BS.searchFirstEqual(arr, 5));
        System.out.println("Last Equal            :"+BS.searchLastEqual(arr, 5));
        System.out.println("First Equal or Larger :"+BS.searchFirstEqualorLarger(arr,  5));
        System.out.println("First Larger          :"+BS.searchFirstLarger(arr,  5));
        System.out.println("Last Equal or Smaller :"+BS.searchLastEqualorSmaller(arr,  5));
        System.out.println("Last Smaller          :"+BS.searchLastSmaller(arr,  5));

image