二分查找算法的实现

前言

使用二分查找算法的前提是查找的序列有序。

递归实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13

int binary_search01(int start,int end,int key,int a[]){
    if (start<=end) {
        int mid = (start+end)/2;
        if (key>a[mid]) {
            return binary_search01(mid+1, end, key, a);
        }else if(key< a[mid]){
            return binary_search01(start, mid-1, key, a);
        }else{
            return mid;
        }
    }
    return -1;
}

非递归实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

int binary_search02(int start,int end,int key,int a[]){
    int mid;
    while (start<=end) {
        mid = (start+end)/2;
        if (key>a[mid]) {
            start = mid+1;
        }else if(key< a[mid]){
            end = mid - 1;
        }else{
            return mid;
        }
    }
    return -1;
}

Comments