| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛

[题] 二分搜索
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 ]。

DO IT YOURSELF !

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

DO IT YOURSELF !

```#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];
}```

```#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;
}
```
• 6
• 1/1页
• 1