基于数组的折半查找

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

//折半查找的迭代实现
int BinarySearch(int *a, const int x, const int n)
{
    int left=0;
    int right = n-1;
    while(left<=right)
    {
        int middle = (left+right)/2;
        if(x<a[middle])
            right=middle-1;
        else if(x>a[middle])
            left = middle+1;
        else
            return middle;
    }
    return -1;
}

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

//折半查找的递归实现
int BinaryFind(int *a, const int x, const int left, const int right)
{
    if(left<=right)
    {
        int middle = (left+right)/2;
        if(x<a[middle])
            return BinaryFind(a,x,left,middle-1);
        else if(x>a[middle])
            return BinaryFind(a,x,middle+1,right);
        else
            return middle;
    }
    return -1;
}