二分查找——递归+非递归实现（c语言）_二分查找的非递归实现

要求：

给定n个从小到大排好序的整数序列Data[]以及待查找整数X，找到X在Data[]中的下标

若Data[i]=X，则返回i，否则返回失败标志NotFound

二分法：

现在找到序列的中点Data[Mid],与X进行比较

若相等则返回中点下标Mid

若X<Data[Mid] ,则在左边的子序列中查找X

若X>Data[Mid],则在右边的子序列中查找X

递归实现代码：

#include<stdio.h>
#include<stdlib.h>
 
#define NotFound -1
#define MAXSIZE 100 
//线性表的定义 (顺序存储)
typedef int Position;
typedef int ElementType;
typedef struct LNode *List;
struct LNode{
    ElementType Data[MAXSIZE];
    Position Last;//保证数组Data[]中最后一个元素的位置 
};
 
//函数接口 
Position BS(List L,ElementType X,Position Left,Position Right); 
Position BinarySearch(List L,ElementType X);
 
//递归实现 
//T(N)=O(logN) ,S(N)=O(logN)
Position BS(List L,ElementType X,Position Left,Position Right){
    //left和right 为当前要处理的L->Data[]中最左和最右的下标值
    if(Left>Right)//当前范围内没有元素了
        return NotFound;
    int Mid=(Left+Right)/2;
    if(X<L->Data [Mid])
        return BS(L,X,Left,Mid-1);//调整有边界 
    else if(X>L->Data [Mid])
        return BS(L,X,Mid+1,Right); //调整左边界
    else 
        return Mid; //找到了，返回数组元素的下标 
}
Position BinarySearch(List L,ElementType X){
    return BS(L,X,1,L->Last);
}
 
List MakeEmpty()
{
    List L;
    L=(List)malloc(sizeof(struct LNode));
    L->Last =-1;
    return L;
 } 
 
int main()
{
    //初始化 
    List L=MakeEmpty(); 
    
    int i;
    ElementType X;
    
    //输入 
    printf("请输入10个元素：\n"); 
    for(i=0;i<10;i++){
        scanf("%d",&L->Data[i]);
        L->Last ++;
    }
    
    //二分查找
    printf ("请输入需要查找的元素：\n");
    scanf("%d",&X);
    Position p=BinarySearch(L,X);
    printf("%d在数组中的下标为%d\n",X,p);
     
    return 0;
}

非递归实现代码：

#include<stdio.h>
#include<stdlib.h>
 
#define NotFound -1
#define MAXSIZE 100 
//线性表的定义 (顺序存储)
typedef int Position;
typedef int ElementType;
typedef struct LNode *List;
struct LNode{
    ElementType Data[MAXSIZE];
    Position Last;//保证数组Data[]中最后一个元素的位置 
};
 
//函数接口 
Position BinarySearch(List L,ElementType X);
 
 
//非递归实现 
//T(N)=O(logN) ,S(N)=O(1)
Position BinarySearch(List L,ElementType X){
    Position Left,Right,Mid;
    Left=1;        //初始左边界下标值 
    Right=L->Last ;//初始右边界下标值 
    while(Left<=Right){
        Mid=(Left+Right)/2;//计算中间元素坐标 
        if(X<L->Data [Mid])
            Right=Mid-1;//调整右边界
        else if(X>L->Data [Mid])
            Left=Mid+1;//调整左边界
        else 
            return Mid; //找到了，返回数组元素的下标 
    } 
    return NotFound;//没找到，返回不成功的标志 
}
 
List MakeEmpty()
{
    List L;
    L=(List)malloc(sizeof(struct LNode));
    L->Last =-1;
    return L;
 } 
 
int main()
{
    //初始化 
    List L=MakeEmpty(); 
    
    int i;
    ElementType X;
    
    //输入 
    printf("请输入10个元素：\n"); 
    for(i=0;i<10;i++){
        scanf("%d",&L->Data[i]);
        L->Last ++;
    }
    
    //二分查找
    printf ("请输入需要查找的元素：\n");
    scanf("%d",&X);
    Position p=BinarySearch(L,X);
    printf("%d在数组中的下标为%d\n",X,p);
     
    return 0;
}

运行：