6-13 折半查找

题目链接：6-13 折半查找

一. 题目

1. 题目

2. 裁判程序样例

3. 输入输出样例

4. 限制

二、代码

1. 代码实现

int  Search_Bin(SSTable T, KeyType k) {
    int min = 1, max = T.length, mid;
    // 长度为0时，无需查找
    // 可删除, while循环的条件已经对此做了判断
    if (max == 0) {
        return 0;
    }
     // 小于最小值或大于最大值时，无需查找
     // 此部分可放置在while循环内，可提前结束循环
    if (T.R[min].key > k || T.R[max].key < k) {
        return 0;
    }
    while(min <= max) {
        mid = (min + max) / 2;
        /*
        // 此部分不属于折半查找，可提前结束循环
        if (T.R[min].key == k) {
            return min;
        } else if (T.R[max].key == k) {
            return max;
        }
        */
        if (T.R[mid].key == k) {
            return mid;
        } else if (T.R[mid].key < k) {
            min = mid + 1;
        } else if (T.R[mid].key > k) {
            max = mid - 1;
        }
    }
    return 0;
}
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

2. 提交结果

三、总结

1. 实现了查找算法中的折半查找