基础的二分查找代码过于简单就不写了，这里主要记录几种变形题，在面试题中出现过：

  • 查找第一个出现指定值
  • 查找最后一个出现的指定值
  • 查找第一个大于指定值的值
  • 查找最后一个小于指定值的值

对于二分查找的前提都是有序的，所以在使用二分查找之前需要先进行排序，由此可见二分差查找不适用于那些频繁修改的数据集

（直接贴代码了，代码量不大，看着就能理解）

查找第一个出现指定值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int find_fist_value(int arr[], int len, int value) {

    int low = 0;
    int high = len - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (arr[mid] > value) {
            high = mid - 1;
        } else if (arr[mid] < value) {
            low = mid + 1;
        } else {
            if ((mid == 0) || (arr[mid - 1] != value)) {
                return mid;
            } else {
                high = mid - 1;
            }
        }
    }
    return -1;
}

查找最后一个出现的指定值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int find_last_value(int arr[], int len, int value) {

    int low = 0;
    int high = len - 1;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        if (arr[mid] > value) {
            high = mid - 1;
        } else if (arr[mid] < value) {
            low = mid + 1;
        } else {
            if ((mid == len - 1) || (arr[mid + 1] != value)) {
                return mid;
            } else {
                low = mid + 1;
            }
        }
    }
    return -1;
}

查找第一个大于指定值的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int find_the_fist_bigger_value(int arr[], int len, int value) {

    int low = 0;
    int high = len - 1;

    cout << "你想要找的是第一个大于 " << value << " 的值" << endl;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        cout << "当前 mid 的值为 : arr[" << mid << "] -- " << arr[mid] << endl;
        if (arr[mid] > value) {
            if (mid == 0 || arr[mid - 1] <= value) {
                return mid;
            } else {
                high = mid - 1;
            }
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

查找最后一个小于指定值的值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int find_the_last_smaller_value(int arr[], int len, int value) {

    int low = 0;
    int high = len - 1;

    cout << "你想要找的是最后一个小于 " << value << " 的值" << endl;

    while (low <= high) {
        int mid = low + ((high - low) >> 1);
        cout << "当前 mid 的值为 : arr[" << mid << "] -- " << arr[mid] << endl;
        if (arr[mid] < value) {
            if (mid == len - 1 || arr[mid + 1] >= value) {
                return mid;
            } else {
                low = mid + 1;
            }
        } else {
            high = mid - 1;
        }
    }

    return -1;
}