首页 > 代码库 > 【二分查找】及相关问题

【二分查找】及相关问题

1.旋转数组中找最小值

顺序查找时间复杂度为O(n),二分查找时间复杂度为O(logn)

技术分享
 1 // rotateArrMin.cpp : 定义控制台应用程序的入口点。 2 // 3  4 #include "stdafx.h" 5 #include <iostream> 6 using namespace std; 7  8 void MinInOrder(int *arr,int begin,int end) 9 {10     int result = arr[begin];11     for(int i = begin+1; i < end;i++)12         result = min(result,arr[i]);13     cout<<result<<endl;14 }15 16 void Min(int* arr,int len)17 {18     if(arr == NULL || len <= 0)19         return;20 21     int begin = 0;22     int end = len - 1;23     int middle = begin;24     int result = 0;25     //强middle初始化为begin,在原数组中也能返回第一个数即最小值,(此时旋转了0)26     while(begin <= end)27     {28         if(end - begin == 1)29         {30             result = arr[end];31             break;32         }33         middle = (begin + end)>>1;34 35         if(arr[begin] == arr[middle] && arr[middle] == arr[end])36             MinInOrder(arr,begin,end);37         //处理01111的旋转,11101等38 39         if(arr[middle] >= arr[begin])40             begin = middle;41         else if(arr[middle] <= arr[end])42             end = middle;43     }44     cout<<result<<endl;45 }46 47 int _tmain(int argc, _TCHAR* argv[])48 {49     int arr[] = {3,4,5,1,2};50     int len = 5;51     Min(arr,len);52     system("pause");53     return 0;54 }
View Code

 

【二分查找】及相关问题