随笔 - 89  文章 - 118  trackbacks - 0
<2012年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

留言簿(16)

随笔分类(56)

随笔档案(89)

文章分类

推荐博客

搜索

  •  

最新随笔

最新评论

阅读排行榜

http://blog.sina.com.cn/s/blog_a2498b5b01014bsg.html

题目描述:

     一个循环有序数组(如:3,4,5,6,7,8,9,0,1,2),不知道其最小值的位置,要查找任一数值的位置。要求算法时间复杂度为log2(n)。


问题分析:

    我们可以把循环有序数组分为左右两部分(以mid = (low+high)/ 2为界),由循环有序数组的特点知,左右两部分必有一部分是有序的,我们可以找出有序的这部分,然后看所查找元素是否在有序部分,若在,则直接对有序部分二分查找,若不在,对无序部分递归调用查找函数。

代码如下:

    #include <iostream>

    using namespace std;

    int binarySearch(int a[],int low,int high,int value)  //二分查找
    {
        if(low>high)
            return -1;

        int mid=(low+high)/2;

        if(value==a[mid])
            return mid;
        else if(value>a[mid])
            return binarySearch(a,mid+1,high,value);
        else
            return binarySearch(a,low,mid-1,value);
    }

    int Search(int a[],int low,int high,int value)     //循环有序查找函数
    {
        int mid=(low+high)/2;

        if(a[mid]>a[low])       //左有序
        {
            if(a[low]<=value && value<=a[mid] )        //说明value在左边,直接二分查找
            {
                return binarySearch(a,low,mid,value);
            }

            else                                       //value在右边
            {
                return Search(a,mid+1,high,value);
            }
        }
        else                    //右有序
        {
            if(a[mid]<=value && value<=a[high])
            {
                return binarySearch(a,mid,high,value);
            }
            else
            {
                return Search(a,low,mid-1,value);
            }
        }
    }

    int main()
    {
        int a[]={3,4,5,6,7,8,9,0,1,2};

        cout<<Search(a,0,9,0)<<endl;

        return 0;
    }

posted on 2012-12-26 16:15 胡满超 阅读(332) 评论(0)  编辑 收藏 引用 所属分类: 算法转载

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理