漫谈递归:二分查找算法的递归实现

用递归写一个二分查找
服务器君一共花费了738.996 ms进行了7次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

还有一个典型的递归例子是对已排序数组的二分查找算法。

现在有一个已经排序好的数组,要在这个数组中查找一个元素,以确定它是否在这个数组中,很一般的想法是顺序检查每个元素,看它是否与待查找元素相同。这个方法很容易想到,但它的效率不能让人满意,它的复杂度是O(n)的。现在我们来看看递归在这里能不能更有效。

还是考虑上面的两个条件:

  • 第一:这个问题是否可以分解为形式相同但规模更小的问题?
  • 第二:如果存在这样一种分解,那么这种分解是否存在一种简单情境?

考虑条件一:我们可以这样想,如果想把问题的规模缩小,我们应该做什么?

可以的做法是:我们先确定数组中的某些元素与待查元素不同,然后再在剩下的元素中查找,这样就缩小了问题的规模。那么如何确定数组中的某些元素与待查元素不同呢? 考虑到我们的数组是已经排序的,我们可以通过比较数组的中值元素和待查元素来确定待查元素是在数组的前半段还是后半段。这样我们就得到了一种把问题规模缩小的方法。

接着考虑条件二:简单情境是什么呢?

容易发现,如果中值元素和待查元素相等,就可以确定待查元素是否在数组中了,这是一种简单情境,那么它是不是唯一的简单情境呢? 考虑元素始终不与中值元素相等,那么我们最终可能得到了一个无法再分的小规模的数组,它只有一个元素,那么我们就可以通过比较这个元素和待查元素来确定最后的结果。这也是一种简单情境。

好了,基于以上的分析,我们发现这个问题可以用递归来解决,二分法的代码如下:

#include "stdio.h"
#include "stdlib.h"

void selectionSort(int data[], int count);
int binary_search(int *a, int n, int key);

void main()
{
    int i, key, rs;
    int arr[10];
    int count;

    printf("排序前数组为:");
    srand((int)time(0));
	for(i=0; i < 10; i++)
	{
	    arr[i] = rand()%100;
	    printf("%d ",arr[i]);
	}

    count = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, count);

    printf("\n排序后数组为:");
    for(i=0; i < 10; i++)
	{
	    printf("%d ", arr[i]);
	}

    printf("\n请输入要查找的数字:");
    scanf("%d",&key);

    rs = binary_search(arr, 10, key);
    printf("%d ", rs);
}

void selectionSort(int data[], int count)
{
    int i, j, min, temp;
    for(i = 0; i < count; i ++) {
        /*find the minimum*/
        min = i;
        for(j = i + 1; j < count; j ++)
            if(data[j] < data[min])
                min = j;
        temp = data[i];
        data[i] = data[min];
        data[min] = temp;
    }
}

int binary_search(int *data, int n, int key)
{
    int mid;
    if(n == 1){
        return (data[0] == key);
    }else{
        mid = n/2;
        printf("mid=%d\n", data[mid]);
        if(data[mid-1] == key)
            return 1;
        else if(data[mid-1] > key)
        {
            printf("key %d 比 data[mid-1] %d 小,取前半段 \n", key, data[mid-1]);
            return binary_search(&data[0], mid, key);
        }
        else
        {
            printf("key %d 比 data[mid-1] %d 大,取后半段 \n", key, data[mid-1]);
            return binary_search(&data[mid], n - mid, key);
        }
    }
}

程序运行结果:

排序前数组为:53 27 26 99 20 17 15 25 23 63
排序后数组为:15 17 20 23 25 26 27 53 63 99
请输入要查找的数字:20
mid=26
key 20 比 data[mid-1] 25 小,取前半段
mid=20
key 20 比 data[mid-1] 17 大,取后半段
mid=23
1

这个算法的复杂度是O(logn)的,显然要优于先前提到的朴素的顺序查找法。

延伸阅读

此文章所在专题列表如下:

  1. 漫谈递归:递归的思想
  2. 漫谈递归:递归需要满足的两个条件
  3. 漫谈递归:字符串回文现象的递归判断
  4. 漫谈递归:二分查找算法的递归实现
  5. 漫谈递归:递归的效率问题
  6. 漫谈递归:递归与循环
  7. 漫谈递归:循环与迭代是一回事吗?
  8. 递归计算过程与迭代计算过程
  9. 漫谈递归:从斐波那契开始了解尾递归
  10. 漫谈递归:尾递归与CPS
  11. 漫谈递归:补充一些Continuation的知识
  12. 漫谈递归:PHP里的尾递归及其优化
  13. 漫谈递归:从汇编看尾递归的优化

本文地址:http://www.nowamagic.net/librarys/veda/detail/2317,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2317

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《高性能网站建设指南》 桑德斯 (Steve Sounders) (作者), 刘彦博 (译者)

《高性能网站建设指南》结合Web2.0以来Web开发领域的最新形势和特点,介绍了网站性能问题的现状、产生的原因,以及改善或解决性能问题的原则、技术技巧和最佳实践。重点关注网页的行为特征,阐释优化Ajax、CSS、JavaScript、Flash和图片处理等要素的技术,全面涵盖浏览器端性能问题的方方面面。在《高性能网站建设指南》中,作者给出了14条具体的优化原则,每一条原则都配以范例佐证,并提供了在线支持。全书内容丰富,主要包括减少HTTP请求、ExpiresHeader技术、Gzip组件、CSS和JavaScript最佳实践、关闭ETags的技巧、Ajax缓存技术和最小化技术等。

更多计算机宝库...