Note: This article is available in Chinese only. 本文暂无英文版本。
View original
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 {
7
8public:
9
10 int bin(int n,int tar,vector<int>& nums)
11 {
12 int l = 0 ;
13 int r = n-1;
14 while (l<=r)
15 {
16 int mid = (l+r)>>1;
17 if (nums[mid]==tar) return mid;
18 if (nums[mid]<nums[r])
19 {
20 if (nums[mid]<tar && tar<=nums[r]) l = mid + 1;
21 else r = mid -1;
22 }
23 else
24 {
25 if (nums[l]<=tar && tar < nums[mid]) r = mid - 1;
26 else l = mid + 1;
27 }
28 }
29 return -1;
30 }
31
32 int search(vector<int>& nums, int target) {
33 int n = nums.size();
34 int res = bin(n,target,nums);
35 return res;
36
37
38 }
39
40};