递归与分治:二分查找

时间:2021-09-05 14:43:40

二分查找只是一个递归的问题,并不体现分治法的思想。


算法前件:带查找序列有序(从左到右,非减序或非升序)

基本思想:先将待查元素与中间元素比,若比中间元素大,则在序列的后一半继续查找;若比中间元素小,则在序列的前一半继续查找。

算法描述:

                  1.与待查序列第一个元素比,若等于,则返回该元素下标,结束比较

                  2.与待查序列最后一个元素比,若等于,则返回该元素下标,结束比较

                  3.与待查序列中间元素m比,

                            若等于,则返回该元素下标,结束比较

                            若比m大,则在将序列范围确定为元素m至最后一个元素,返回步骤一执行,继续上述过程。

                           若比m小, 则在将序列范围确定第一个元素至元素m中间,返回步骤一执行,继续上述过程。

递归结束:待查序列为空

 

核心代码:

int A[100];
int aim;
//low,high分别表示待查序列的起点下标和终点下标
int find(int low,int high)
{
    if(low>high)
        return -1;
    
    int mid=(low+high)/2;
    if(A[low]==aim)
        return low;
    if(A[high]==aim)
        return high;
    if(A[mid]==aim)
        return aim;
    if(A[mid]<aim)
        return find(mid+1,high-1);
    else
        return find(low+1,mid-1);
}