二分查找算法基础

一.二分查找

二分查找，又叫“折中查找”，其通过问题的性质，每次将问题规模缩小一半，对应的时间复杂度为O(logN)。二分查找不仅能用作数组元素的查找，还可用于单调函数的求解。

对于二分查找算法，它包含head（头指针）， tail（尾指针），  mid三个变量，这里的头尾指针其实并不是指针，一般为整型，表示所求问题的范围的边界，通过判断查找的数据是否在这两个范围内（指的是从head到mid和从mid到head两个范围），来缩小问题规模。

二.二分查找的模版

例如，在进行数组数据的查找时，可以通过循环的方式实现。

其中二分查找的函数返回值为，对应数据的数组下标，如果找不到，返回-1.

#include <stdio.h>
#define max_n 1000
int binary_search(int *arr, int n, int k){
    int head = 0, tail = n - 1, mid;
    while(head <= tail){
        mid = (head + tail) / 2;
        if(arr[mid] == k) return mid;
        if(arr[mid] > k) tail = mid - 1;
        else head = mid + 1; 
    }
    return -1;
}
int main(){
    int arr[max_n + 5] = {0};
    int n, k;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    while(scanf("%d", &k) != EOF){
        int result = binary_search(arr, n, k);
        printf("%d is %d from arr\n", k, result);
    }
    return 0;
}

也可以利用递归的方式实现

#include <stdio.h>
#define max_n 1000
int binary_search(int *arr, int head, int tail, int k){
    int mid;
    while(head <= tail){
        mid = (head + tail) / 2;
        if(arr[mid] == k) return mid;
        if(arr[mid] > k) return binary_search(arr, head, mid - 1, k);
        else return binary_search(arr, mid + 1, tail, k); 
    }
    return -1;
}
int main(){
    int arr[max_n + 5] = {0};
    int n, k;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
        scanf("%d", &arr[i]);
    }
    while(scanf("%d", &k) != EOF){
        int head = 0, tail = n - 1;
        int result = binary_search(arr, head, tail, k);
        printf("%d is %d from arr\n", k, result);
    }
    return 0;
}

利用递归实现，虽然可以使代码更简洁，但其涉及到出栈入栈操作，运行速度会变慢，如果数据范围处理不当，还有可能爆栈，所以一般使用第一种实现即可。

三.举例

利用二分查找判断一个数是不是立方数。

#include <stdio.h>
int cube(int x){
    return x * x * x; 
}
int binary_search(int x){
    int head = 1, tail = x - 1, mid;
    while(head <= tail){
        mid = (head + tail) / 2;
        if(cube(mid) == x) return 1;
        if(cube(mid) < x) head = mid + 1;
        else tail = mid - 1;
    }
    return 0;
}
int main(){
    int k;
    while(scanf("%d", &k) != EOF){
        if(binary_search(k)) printf("%d是一个立方数\n", k);
        else printf("%d不是一个立方数\n", k);
    }

    return 0;
}

在这里因为cube函数是一个单调函数，所以可以用二分查找解决该问题。