这4个题都是针对旋转的排序数组。其中153、154是在旋转的排序数组中找最小值，33、81是在旋转的排序数组中找一个固定的值。且153和33都是没有重复数值的数组，154、81都是针对各自问题的版本1增加了有重复数值的限制条件。
153、154都需要考虑是否旋转成和原数组一样的情况，特别的，154题还需要考虑10111和11101这种特殊情况无法使用二分查找。
33、81则不用考虑这些情况。
找最小值的题主要是利用最小值小于他前一个位置的数，同时也小于后一个位置的数
start是前面升序的最后一个，end是后面升序的第一个, 只剩两个时，end就代表了那个最小值
153. Find Minimum in Rotated Sorted Array
class Solution {
public:
int findMin(vector<int>& nums) {
int start = ;
int end = nums.size() - ;
int mid;
if(nums[start] < nums[end])
return nums[start];
while(start + < end){
mid = start + (end - start)/;
if(nums[mid] < nums[start])
end = mid;
else
start = mid;
}
return nums[end];
}
};
154. Find Minimum in Rotated Sorted Array II
class Solution {
public:
int findMin(vector<int>& nums) {
int start = ;
int end = nums.size() - ;
int mid = start + (end - start)/;
if(nums[start] < nums[end])
return nums[start];
if(nums[start] == nums[end] && nums[start] == nums[mid]){
int min_num = INT_MAX;
for(int i = ;i < nums.size();i++){
if(nums[i] < min_num)
min_num = nums[i];
}
return min_num;
}
while(start + < end){
mid = start + (end - start)/;
if(nums[mid] < nums[start])
end = mid;
else
start = mid;
}
return nums[end];
}
};
33. Search in Rotated Sorted Array
这个题和剑指上旋转数组求最小值有点不一样，还是用二分查找的方法做，但条件判断较为繁琐。首先明确一点，无论怎么分，左右两侧总有一个是有序的，并且一般情况左侧是大的数，右侧是小的数。mid小于target的时候，相当于要找一个更大的数，所以想法是先排除一般情况下小的数，如果start < mid，证明这是个升序，那只可能在右侧；如果start > mid，证明右侧是升序，只要和最大的比较，也就是end，如果比end小，说明数字在右侧，如果比end大，说明数字在左侧，因为比最大的都大了。
总体上就是当target大于mid的时候，就去比较可能出现大数的左侧区间，如果是升序，那就能排除；如果左侧区间不是升序，则右侧是升序，需要拿这个升序的最大值和mid进行比较来确定下一个区间
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty())
return -;
int start = ;
int end = nums.size() - ;
int mid;
while(start + < end){
mid = start + (end - start)/;
if(nums[mid] == target)
return mid;
else if(nums[mid] < nums[end]){
if(nums[mid] < target && nums[end] >= target)
start = mid;
else
end = mid;
}
else{
if(nums[mid] > target && nums[start] <= target)
end = mid;
else
start = mid;
}
}
if(nums[start] == target)
return start;
if(nums[end] == target)
return end;
return -;
}
};
自己的写法：
其实是可以使用mid - 1,mid+1的，因为之前做了nums[mid] == target的判断，这说明mid不可能等于target，所以可以去掉。
最需要注意的是，在判断单调区间时，start、end与target的比较一定是<=或者>=，必须考虑边界相等的情况
总体的思路就是：判断单调区间，然后判断target属于不属于这个区间，属于就在这个区间找，不属于就去另一个区间找。判断属于不属于，就是拿target与这个区间的边界进行判断。
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty())
return -;
int start = ,end = nums.size() - ;
while(start + < end){
int mid = start + (end - start)/;
if(nums[mid] == target)
return mid;
else if(nums[start] < nums[mid]){
if(target < nums[mid] && nums[start] <= target)
end = mid - ;
else
start = mid + ;
}
else{
if(target > nums[mid] && nums[end] >= target)
start = mid + ;
else
end = mid - ;
}
}
if(nums[start] == target)
return start;
if(nums[end] == target)
return end;
return -;
}
};
81. Search in Rotated Sorted Array II
这个题与Search in Rotated Sorted Array不同在于，这个题里面可能包含重复的数字。
代码上的区别主要是在进行单调区间判断的时候，即如果start或者end与mid的值相等的情况要单独列出来，列出来的方式是start++，mid--
Search in Rotated Sorted Array直接else其实是包括了=这种情况，但是因为本身数组不存在相等的，所以忽略了这个问题。
class Solution {
public:
bool search(vector<int>& nums, int target) {
if(nums.empty())
return false;
int start = ;
int end = nums.size() - ;
int mid;
while(start + < end){
mid = start + (end - start)/;
if(nums[mid] == target)
return true;
else if(nums[mid] < nums[end]){
if(nums[mid] < target && nums[end] >= target)
start = mid;
else
end = mid;
}
else if(nums[mid] > nums[end]){
if(nums[mid] > target && nums[start] <= target)
end = mid;
else
start = mid;
}
else
end--;
}
if(nums[start] == target)
return true;
if(nums[end] == target)
return true;
return false;
}
};
http://www.cnblogs.com/grandyang/p/4325840.html
704. Binary Search
class Solution {
public:
int search(vector<int>& nums, int target) {
if(nums.empty())
return -;
int start = ;
int end = nums.size() - ;
int mid;
while(start + < end){
mid = start + (end - start)/;
if(nums[mid] == target)
return mid;
else if(nums[mid] < target)
start = mid;
else
end = mid;
}
if(nums[start] == target)
return start;
if(nums[end] == target)
return end;
return -;
}
};