| 网站首页 | 业界新闻 | 小组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 745 人关注过本帖
标题:[题] 二分搜索
只看楼主 加入收藏
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:334
帖 子:6880
专家分:40011
注 册:2011-1-18
结帖率:90.91%
  已结贴   问题点数:100  回复次数:5   
[题] 二分搜索
Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

一个有序的无重复数字的整型数组,从某处断开,前后互调。例如
[ 0 1 2 | 4 5 6 7 ] 从 2 和 4 中间断开,前后互调得 [ 4 5 6 7 0 1 2 ]。
现在给你一个这样的数组(原本有序,后被前后互调),要求你快速的找到数组中的最小值。
例如给你 [ 4 5 6 7 0 1 2 ],你应该返回 0
例如给你 [ 1 2 ],你应该返回 1

提示:使用二分法以提高效率

搜索更多相关主题的帖子: minimum become 
【推荐】大型监控、工控、组态VC++./C#源码组件库2019下载!
【推荐】超50万数控、建模仿真、电力VC++/.NET图形源码库下载!
【推荐】专业CAD\GIS\业务流程VC++/C#可视化图形软件源码库下载!
2015-08-13 13:20
wp231957
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:神界
等 级:版主
威 望:398
帖 子:13394
专家分:51686
注 册:2012-10-18
  得分:25 
遍历啊遍历  我只会遍历

DO IT YOURSELF !
2015-08-13 13:54
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:334
帖 子:6880
专家分:40011
注 册:2011-1-18
  得分:0 
以下是引用wp231957在2015-8-13 13:54:31的发言:

遍历啊遍历  我只会遍历
以 [ 4 5 6 7 0 1 2 ] 为例,左边4,右边2,正中间7,于是可以断定最小数应该在这个数组的后一半中,一下子排除掉了一半,就是二分法
2015-08-13 14:04
wp231957
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:神界
等 级:版主
威 望:398
帖 子:13394
专家分:51686
注 册:2012-10-18
  得分:25 
要是数据量特别大 还可以   否则,以楼主的例子而言  我用肉眼就能判断出最小数是0  根本就不需要电脑去遍历 去二分

回头还是说这个例子:

arry[0]=4 arr[max]=2  arr[mid]=7  可以判断4-7是有序 7--2 是乱序(那能判断min在7--2中  那么下一步判断呢  数列就是偶数个了 不存在arr[mid]了

DO IT YOURSELF !
2015-08-13 14:14
jklqwe111
Rank: 8Rank: 8
等 级:贵宾
威 望:24
帖 子:267
专家分:903
注 册:2014-4-13
  得分:25 
程序代码:
#include<stdio.h>
int main ()
{ 
    int data[]={4 ,5, 6 ,7 ,12 ,0 ,2 };
    int data01[]={1,2,3};
    int f(int data[],int n);
    printf("%d\n",f(data,7));
    printf("%d\n",f(data01,3));
    return 0;

}
int f(int data[],int n)
{
  int low,hig,cet,key;
  key=data[0];
  if(key<data[n-1]) return key;
  low=0;
  hig=n-1;
  while(hig-low>1)
  {
    cet=low+(hig-low)/2;
    if(data[cet]>key) low=cet;
    else hig=cet;
  }
  return data[hig];
}
2015-08-13 14:18
kenierlee
Rank: 6Rank: 6
等 级:侠之大者
威 望:3
帖 子:58
专家分:474
注 册:2015-7-28
  得分:25 
程序代码:
#include <stdio.h>

int search(int *array, int size)
{
    int low = 0, high = size, mid1, mid2, mid3;
    if (size == 1)
        return array[0];
    else if (size == 2)
        return array[0] < array[1] ? array[0] : array[1];
    while (low < high)
    {
        mid1 = (low + high)/2;
        if (array[mid1-1] > array[mid1])
            break;
        mid2 = (low + mid1)/2;
        mid3 = (mid1 + 1 + high)/2;
        array[mid2] > array[mid3] ? low = mid1 + 1 : high = mid1;
    }
    return array[mid1];
}

int main(void)
{
    int a[] = { 4, 5, 6, 7, 0, 1, 2 };
    int b[] = { 1, 2 };
    printf("%d\n", search(a, sizeof a/sizeof(int)));
    printf("%d\n", search(b, sizeof b/sizeof(int)));
    return 0;
}
2015-08-13 16:10
快速回复:[题] 二分搜索
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.091125 second(s), 8 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved