查找算法

1. 二分查找算法

循环实现

int binarySearch(int *a, int len, int x) {
    int low = 0;
    int high = len-1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;
        if (a[mid] < x)
            low = mid + 1;
        else if (a[mid] > x)
            high = mid - 1;
        else {
            printf("found: a[%d]=%d\n", mid, a[mid]);
            return mid;
        }
    }
    printf("notfound\n");
    return -1;
}

递归实现

int binarySearchRecursive(int *a, int x, int low, int high) {
    if (low > high)
        return -1;

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

int binarySearchRecursive(int *a, int len, int x) {
    int ind = binarySearchRecursive(a, x, 0, len-1);
    if (ind == -1)
        printf("notfound\n");
    else
        printf("found: a[%d]=%d\n", ind, a[ind]);
    return ind;
}