leetcode 33. Search in Rotated Sorted Array (无重复数的旋转数组找定值)
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
思路：找规律。。。二分。。。
0 1 2 3 4 5 6
1 2 3 4 5 6 0
2 3 4 5 6 0 1
3 4 5 6 0 1 2
4 5 6 0 1 2 3
5 6 0 1 2 3 4
6 0 1 2 3 4 5
观察发现。。。a[mid]<a[r]的时候，后半段有序;
a[mid]>a[r]的时候，前半段有序。。
然后根据有序区间的端点值，确定tar是在该有序区间，还是在另一半区间。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 14时17分03秒
4File Name :33.cpp
5************************************************ */
6class Solution {
public:
1 int bin(int n,int tar,vector<int>& nums)
2 {
3 int l = 0 ;
4 int r = n-1;
5 while (l<=r)
6 {
7 int mid = (l+r)>>1;
8 if (nums[mid]==tar) return mid;
9 if (nums[mid]<nums[r])
10 {
11 if (nums[mid]<tar && tar<=nums[r]) l = mid + 1;
12 else r = mid -1;
13 }
14 else
15 {
16 if (nums[l]<=tar && tar < nums[mid]) r = mid - 1;
17 else l = mid + 1;
18 }
19 }
20 return -1;
21 }
1 int search(vector<int>& nums, int target) {
2 int n = nums.size();
3 int res = bin(n,target,nums);
4 return res;
}
};