二分搜索

 

运用

查找数

求0 1 … 99 100 这个数组中每个元素需几次二分查找才能找到的次数

#include <iostream>

int main() {
    for (int i = 0; i <= 100; i++) {
        // left, right代表左右区间的范围
        int left = 0, right = 100;

        // mid代表中间值, 即查找的起点
        int mid;

        // count代表查找所需的次数
        int cont = 0;

        // 当左区间小于右区间, 说明还有数没查找过的时候
        while (right >= left) {
            cont++;
            // 初始化起点的位置
            mid = (left + right) >> 1;

            if (i == mid) {
                break;
            }
            // 若该值小于中间值, 则缩小区间至[l, mid-1]
            if (i < mid) {
                right = mid - 1;
            }
            // 若该值大于中间值, 则缩小区间至[mid+1, r]
            if (i > mid) {
                left = mid + 1;
            }
        }
        std::cout << i << " " << "一共查找了" << cont << "次" << std::endl;
    }
    return 0;
}

查找指定和

从一个数组中找到两个数, 使其和为指定值m

// 遍历数组对每一个a[i], 通过二分查找找到另一个a[mid]
// 通过两者之和与目标值m的比较决定缩小区间的范围
#include<stdio.h>

int main(void) {
    // 标记变量
    bool flag = false;

    // 数组需有序
    int a[n];
    
    // 目标值m
    int m, l, r, mid;
    for (i = 0; i < n; i++){
        l = i;
        r = n - 1;
        while (l < r) {
            mid = (r + l) >> 1;
            // 当找到目标值且不重复时
            if ((m - a[i] == a[mid]) && (i != mid)){
                flag = true;
                ...
                break;
            }
            // 否则缩小范围[mid+1, r]
            if (m - a[i] > a[mid]){
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
    }
    
    if (flag == false){
        ...
    }

    return 0;
}