二分查找算法递归和非递归实现

2021年5月3日 4点热度 0条评论 来源: coding__madman

自己接触和了解过的查找算法总结起来分为3个吧:

1. 静态查找(主要是二分查找,效率较高)

2. 动态查找(二叉查找树)

3. 哈希表

首先来说二分查找吧!

基本思想:假设在一个已经排好序的有序序列(N个元素,升序排列),首先让序列N中中间的关键字与需要查找的关键字进行比较,如果相等,则查找成功,否则利用中间位置将序列分成两个子序列,如果待查找的关键字小于中间的关键字,则在前一个子序列中同样的方法进一步查找,如果待查找的关键字大于中间的关键字,则在后一个子序列中同样的方法进一步查找,重复以上过程一直到查找结束!

时间复杂度:O(log(n))

空间复杂度:O(1)

代码示例:

#include <stdio.h>

//二分查找非递归实现 
int BinSearch1(int Array[], int low, int high, int key)
{
    int ret = -1;
    int mid = 0;
    ret = (Array != NULL) && (low >= 0) && (high > low);
    
    printf("Search Key: %d\n", key);
    
    if(ret)
    {
        while(low <= high)
        {
            mid = (low + high)/2;
            
            if(Array[mid] == key)
            {
                ret = mid;
                
                printf("BinSearch1 success!!!\nArray[%d] = key\n", mid);
                
                return ret;
            }
            
            else if(Array[mid] > key)
            {
                high = mid - 1;
            }
            
            else
            {
                low = mid + 1;
            } 
        }
    }
       
    return ret;
}

//二分查找递归实现 
int BinSearch2(int Array[], int low, int high, int key)
{
    int ret = -1;
    int mid = 0;
    ret = (Array != NULL) && (low >= 0) && (high > low);
        
    //if(ret)
    //{
        if(low <= high)
        {
            mid = (low + high)/2;
            
            if(Array[mid] == key)
            {              
                return mid;
            }
 
            if(Array[mid] > key)
                return BinSearch2(Array, low, mid-1, key);
                
            if(Array[mid] < key)
                return BinSearch2(Array, mid+1, high, key);
            else
            {
                return -1;
            }
        }        
    //}
    //return ret;       
}

int main(int argc, char *argv[])
{
  int array[10] = {1, 3, 5, 6, 7, 8, 10, 13, 15, 17};
  int a;
  
  a = BinSearch1(array, 0, 10, 13);
  
  //a = BinSearch2(array, 0, 10, 13);
  
  printf("a = %d\n", a);
  printf("array[%d] = %d\n", a, array[a]);
  printf("Press enter to continue ...");
  
  getchar();	
  return 0;

}


算法思路比较简单,这里就不写注释了,递归代码更简洁,理解起来也稍微容易一点,前提是深刻理解递归思想,递归的专题后边补上!!!


运行效果截图:

递归的代码运行效果和上面的一样!

    原文作者:coding__madman
    原文地址: https://blog.csdn.net/coding__madman/article/details/50839677
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。