首页 > 代码库 > 【二分查找】及相关问题
【二分查找】及相关问题
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 }
【二分查找】及相关问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。