自从做完leetcode上的三道关于二分查找的题后，我觉得它是比链表找环还恶心的题，首先能写出bugfree代码的人就不多，而且可以有各种变形，适合面试的时候不断挑战面试者，一个程序猿写代码解决问题的能力都能在这个过程中考察出来。
在有序数组中寻找等于target的数的下标，没有的情况返回应该插入的下标位置 ：http://oj.leetcode.com/problems/search-insert-position/
public int searchInsert(int[] A, int target) { // Note: The Solution object is instantiated only once and is reused by each test case. int start = 0; int end = A.length-1; while(start<=end){ // 小于等于 int mid = start + (end-start)/2; if(A[mid]<target) start = mid+1; // mid加1 else if(A[mid]>target) end = mid-1; // mid减1 else return mid; } return start; }
在不重复的旋转数组中寻找等于target的数的下标，没有的话返回-1 ：http://oj.leetcode.com/problems/search-in-rotated-sorted-array/
class Solution { public: int search(int A[], int n, int target) { if(n<=0) return -1; int mid; int start=0; int end=n-1; while(start<=end) { mid=(start+end)/2; if(A[mid]==target) return mid; else if(A[mid]>=A[start]) { if(target>=A[start]&&target<A[mid]) end=mid-1; else start=mid+1; } else { if(target>A[mid]&&target<=A[end]) start=mid+1; else end=mid-1; } } return -1; } };
在有重复的旋转数组中判断是否存在等于target的数 ：http://oj.leetcode.com/problems/search-in-rotated-sorted-array-ii/
class Solution { public: bool search(int A[], int n, int target) { if(n==0) return false; int mid; int start=0; int end=n-1; while(start<=end) { mid=(start+end)/2; if(A[mid]==target) return true; else if(A[mid]>A[start]) { if(target<A[mid]&&target>=A[start]) end=mid-1; else start=mid+1; } else if(A[mid]<A[start]) { if(target>A[mid]&&target<=A[end]) start=mid+1; else end=mid-1; } else start++; } return false; } };
旋转数组中查找最小值，当没有重复元素时：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
class Solution { public: int findMin(vector<int> &num) { if(num.empty()) return 0; int s=0; int t=num.size()-1; int mid; while(s<t) { if(num[s]<num[t]) return num[s]; //减少查找次数 mid=(s+t)/2; if(num[mid]<num[t]) t=mid; else s=mid+1; } return num[s]; } };
在有重复元素的时候，查找旋转数组中的最小值：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
class Solution { public: int findMin(vector<int> &num) { if(num.empty()) return 0; int s=0; int t=num.size()-1; while(s<t) { if(num[s]<num[t]) return num[s]; int mid=(s+t)/2; //如果存在重复元素时，进行顺序查找 if(num[s]==num[t]&&num[s]==num[mid]) { int minValue=num[s]; while(s<t) { if(num[s]<minValue) minValue=num[s]; s++; } return minValue; } if(num[mid]>=num[s]) s=mid+1; else t=mid; } return num[s]; } };
