查找

算法

二分查找
时间复杂度O(logn)

int binarysearch(int num[], int x, int N) {
    int low = 0, high = N;
    int mid;
    while(low < high) {
        mid = (low + high) >> 1;
        if (x < num[mid])
            high = mid;
        else if (x > num[mid])
            low = mid+1;
        else
            return mid;
    }
    return -1;
}

插值查找
时间复杂度O(logn)

mid = low+(high-low)*(x-num[low])/(num[high]-num[low]);