递归和非递归的二分查找

2021年09月15日 阅读数:1
这篇文章主要向大家介绍递归和非递归的二分查找,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

思路很是easy,代码凝视已标注ide

 

#include <stdio.h>spa

 

//递归二分查找指针

int binarySearch(int*start,int *end,intfindData){递归

    if (start > end) {      // 递归边界条件it

       return -1;io

    }class

    

    int *mid = start + (end - start)/2;     //依据中间值不断二分缩小待查元素所在范围循环

    if (findData == *mid) {gc

       return *mid;di

    }else if(findData > *mid){

       return binarySearch(mid+ 1, end, findData);

    }else{

       return binarySearch(start,mid - 1, findData);

    }

}

 

//非递归二分查找

int binarySearchRec(int*start,int *end,intfindData){

    if (start == NULL){

       return -1;

    }

    

    while (start <= end) {                 //递归使用边界条件终止递归,非递归使用循环条件来终止

       int *mid = start + (end - start)/2; // 求中间指针

       if (findData == *mid) {

           return *mid;

       }else if(findData > *mid){

           start = mid + 1;

       }else{

           end = mid - 1;

       }

    }

    

    return -1;

}

 

int main(intargc, const char* argv[])

{

    int array[] = {2,4,6,8,10,14,15,19}; // num =8,二分查找的前提条件是元素有序的

    int len = sizeof(array)/sizeof(int);

    printf("递归二分查找binarySearch:%d\n",binarySearch(array,array+ len - 1,100));

    printf("非递归二分查找binarySearchRec:%d\n",binarySearch(array,array + len - 1,19));

    

    return 0;

}