二分查找

二分查找算法，也叫折半查找算法。时间复杂度为 O(logn)，只适用于有序表。

#include <stdio.h>

// 循环实现方式
int binary_search(int *a, int n, int key)
{
    int low, high, mid;
    low = 0;
    high = n - 1;

    while (low <= high) {
        mid = low + (high - low) / 2; // = (low + high) / 2  
        if (key < a[mid]) {
            high = mid - 1;
        } else if (key > a[mid]) {
            low = mid + 1;
        } else {
            return mid;     // mid 即为查找到的位置 
        }
    }
}

// 递归实现方式
int binary_search_internally(int *a, int low, int high, int key);   // 函数声明

int binary_search_2(int *a, int n, int key) 
{
    return binary_search_internally(a, 0, n - 1, key);
} 

int binary_search_internally(int *a, int low, int high, int key) 
{
    if (low > high) return -1;

    int mid = low + (high - low) / 2;
    if (key < a[mid])
        return binary_search_internally(a, low, mid - 1, key);
    else if (key > a[mid])
        return binary_search_internally(a, mid + 1, high, key);
    else
        return mid; 
}

int main()
{
    int a[10] = {1, 16, 24, 35, 47, 59, 62, 73, 88, 99};
    int len = sizeof(a) / sizeof(int);      // 求数组的长度 
    //printf("%d\n", binary_search(a, len, 59));
    printf("%d\n", binary_search_2(a, len, 59));
    return 0;
}