二分查找法及其扩展

二分查找法源代码：

#include<iostream> using namespace std; int binarySearch(int arr[],int len,int goal) { int high = len - 1; int low = 0; int mid = 0; while (high >=low) { mid = (high - low)/2 + low; if (goal > arr[mid]) { low = mid + 1; } else if (goal < arr[mid]) { high = mid - 1; } else { return mid; } } return -1; } int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int goal; int len = sizeof(arr) / sizeof(arr[0]); cin >> goal; int res=binarySearch(arr,len,goal); cout << res << endl; system("pause"); } 在一个非递减有序数组，从左向右旋转之后得到的数组中，查找最小的值，如[0,1,1,1,1,1]->[1,1,1,1,0,1];最小值为0；

在递增时使用二分查找，但是在上例情况下只能遍历查找->详解见剑指offer

#include<iostream> using namespace std; int MiniOrder(int *arr, int low, int high) { int res = arr[low]; for (int i = low + 1; i <= high; i++) { if (res > arr[i]) { res = arr[i]; } } return res; } int findmin(int arr[], int len) { int high = len - 1; int low = 0; int mid=0; while (arr[high] <= arr[low]) { if (high - low == 1) { mid = high; break; } mid = (high +low)/2; if (arr[low] == arr[high] && arr[mid] == arr[low]) { return MiniOrder(arr, low, high); } if (arr[low] <= arr[mid]) { low = mid; } else if (arr[low] >arr[mid]) { high = mid; } } return arr[mid]; } int main() { int arr[] = {1,1,1,1,0,1 }; int len = sizeof(arr) / sizeof(arr[0]); int res=findmin(arr, len); cout << res << endl; system("pause"); }