首页 > 编程 > C > 正文

C 二分查找 递归与非递归的实现代码

2020-01-26 16:20:08
字体:
来源:转载
供稿:网友

复制代码 代码如下:

#include <stdio.h>

int binSearch(int arr[], int low, int high, int key);
int binSearch2(int arr[], int low, int high, int key);
int binSearch3(int arr[],int start,int ends,int key);
int main() {
    int arr[]={3,8,11,15,17,22,23,26,28,29,34};
    //printf("%d",binSearch(arr,0,10,26));
    printf("%d",binSearch3(arr,0,10,26));
    return 1;
}

int binSearch(int arr[], int low, int high, int key) {
    int flag=-1;
    int mid = (low + high) / 2;
    if (low > high) {
        flag= -1;
    } else {

        if (arr[mid] < key) {
            flag= binSearch(arr, mid + 1, high, key);
        } else if (arr[mid]>key) {
            //比如要找的节点在下面这一层   那么这一层会返回下标上来 用flag接住嘛...
            flag= binSearch(arr,low,mid-1,key);//又差一点忘记了用flag取接住返回值了

        } else {
            flag= mid;
        }
    }
    return flag;
}


//ok==============================
int binSearch2(int arr[], int low, int high, int key) {
    int mid = (low + high) / 2;
    if (low > high) {
        return -1;
    } else {

        if (arr[mid] < key) {
            return binSearch2(arr, mid + 1, high, key);
        } else if (arr[mid]>key) {
            return binSearch2(arr,low,mid-1,key);
        } else {
            return mid;
        }
    }

}

int binSearch3(int arr[],int start,int ends,int key){
    int mid=-1;
    while(start<=ends){
        mid=(start+ends)/2;
        if(arr[mid]<key){
            start=mid+1;
        }else if(arr[mid]>key){
            ends=mid-1;
        }else{
            break;
        }
    }//上述循环结束后不一定就是 start>ends的  因为有break语句
    if(start>ends){
        mid=-1;
    }
    return mid;
}       

发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表

图片精选