本文共 1173 字,大约阅读时间需要 3 分钟。
描述:
给一个已经排好序的数组,然后再将他进行旋转(将前n个数搬到末尾)如数组{1,2,3,4,5}旋转为{3,4,5,1,2},求数组中的最小数字。解法:
利用二分查找来提高查找效率。(原理:部分有序)。 代码:特殊情况:
数组{0,1,1,1,1}变为{1,1,1,0,1} 要将这种情况考虑进去。#define _CRT_SECURE_NO_WARNINGS#includeusing namespace std;int MinInOrder(int *arr, int left, int right){ int ret = arr[left]; for (int i = left + 1; i < right; i++) { if (ret > arr[i]) { ret = arr[i]; } } return ret;}int Min(int* arr, int len){ if (arr == NULL || len <= 0) { return -1; } int left = 0; int right = len - 1; int mid = left; while (arr[left] >= arr[right]) { if (right - left == 1)//两个挨着 { mid = right; break; } mid = (left + right) / 2; if (arr[left] == arr[right] && arr[mid]==arr[left]) { return MinInOrder(arr, left, right); } if (arr[mid] >= arr[left]) { left = mid; } else if (arr[mid] <= arr[right]) { right = mid; } } return arr[mid];}int main(){ int arr[5] = { 1,0,1,1,1}; int ret=Min(arr, 5); printf("%d", ret); system("pause"); return 0;}
转载地址:http://iqstd.baihongyu.com/