6-10二分查找

题目描述

实现二分查找算法

题目地址为:https://pintia.cn/problem-sets/15/problems/923

List结构定义 

1
2
3
4
5
6
typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

思考

看结构应该是数组，毕竟Position都是int类型。然后又是线性表，就挨着呗！

二分查找只能用于有序的排列，一次去掉一半。

怎么保证去一半？关键就是用两个值来圈定一个范围，然后取中间的值进行比较。

那这个范围是什么东西？？？这其中就牵涉到了while退出的条件，到底是<= 还是 <。这就需要看自己定义的是开区间还是闭区间。

[2,2] = 1 [2,2) = 0

这里还有关键的一点，为什么一次判断之后更新的范围在边界要加一或者减一。 这也和之前提到的开闭区间有关，如果是开区间那么则不用变化。

查找

要求

L是用户传入的一个线性表，其中ElementType元素可以通过>、==、<进行比较，并且题目保证传入的数据是递增有序的。函数BinarySearch要查找X在Data中的位置，即数组下标（注意：元素从下标1开始存储）。找到则返回下标，否则返回一个特殊的失败标记NotFound。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Position BinarySearch( List L, ElementType X ) {
    int high = L->Last;
    int low  = 1;
    int mid;
    while(high >= low) {
        // 若查找数组很长，就可能会发生越界的情况，那么就应该改为
        // mid = low + (high - low) / 2;
        mid = (high + low) / 2; 
        if (L->Data[mid] == X) {
            return mid;
        } else if (L->Data[mid] > X) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return NotFound;
}

拓展

条件

如果数组中存在相同的元素，当我们需要返回指定位置（最先出现那个数）。那么之前的方式就失效了。

改进代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Position New_BinarySearch( List L, ElementType X ) {
    int high = L->Last;
    int low  = 1;
    int mid;
    while(high >= low) {
        // 若查找数组很长，就可能会发生越界的情况，那么就应该改为
        // mid = low + (high - low) / 2;
        mid = (high + low) / 2; 
        if (L->Data[mid] == X) {
            high = mid - 1;
        } else if (L->Data[mid] > X) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    if (low > L->Last || L->Data[low] != X) {
        return NotFound;
    }
    return low;
}

神奇之处

while循环退出的条件是low == right + 1