二分法查找

二分法查找

思路：

将一些数升序地放在数组中（这里为了方便查找用数组存放数据（下标为零的不用）），确定查找范围，初始时查找范围为整个数组，下标1设为左端点left，数组最后一个元素的下标设为右端点right，中间端点mid为左右端点下标和的一半。将中间端点处的值与待查值e比较，若大于e则说明e在mid左半侧，将右端点移至下标为mid-1处,缩小查找范围,更改mid值为新左右端点下标和的一半;若比较小于e则e在mid右侧，将左端点移至mid+1处，缩小查找范围,更改mid值为新左右端点下标和的一半;若等于e,则找到待查值，返回待查值在数组中的下标。通过不断缩小查找范围至两个数最后确定待查值的位置。

C实现:

    #include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 10
    #define NotFound -1
    
    typedef int ElementType;
    typedef int Position;
    typedef struct LNode *List;
    
    struct LNode {
        ElementType Data[MAXSIZE];
        Position Last;                      //保存线性表中最后一个元素的位置
    };
    
    List ReadInput();                      
    Position BinarySearch( List L, ElementType X );
    
    int main()
    {
        List L;
        ElementType X;
        Position P;
    
        L = ReadInput();               //向数组里写数 
        scanf("%d", &X);               //输入待查找的数 
        P = BinarySearch( L, X );      //二分法查找 
        printf("%d\n", P);             //输出待查数的下标 
    
        return 0;
    }
    
    List ReadInput()
    {
        List A;
        int i;
        
        scanf("%d",&A->Last);
        
        for(i=1;i<=A->Last;i++)            /*元素从下标1开始存储 */
        {
            scanf("%d",&A->Data[i]);
        }
        
        return A;
    }
    
    Position BinarySearch(List L,ElementType X)       //二分法查找 
    { 
        int left=1,right=L->Last,mid=(left+right)/2;
        
        while(right>=left)
        {
             if(X>L->Data[mid])
             {
                 left=mid+1;
                 mid=(left+right)/2;
             }
            else if(X<L->Data[mid])
            {
                 right=mid-1;
                mid=(left+right)/2;
            }
            else
            {
                return mid;
            }
        }
        
        return NotFound;
    }
  

该算法时间复杂度为O(logn),当查找范围十分大时,二分法查找比顺次查找（复杂度O(n)）效率高得多。