62. Search in Rotated Sorted Arr

Description

Suppose a sorted array 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.

Example

Example 1:

Input: [4, 5, 1, 2, 3] and target=1,

Output: 2.

Example 2:

Input: [4, 5, 1, 2, 3] and target=0,

Output: -1.

Challenge

O(logN) time

思路：

看到题目要求就猜到用二分法， 但是这个题的难点在于无法把数据分为合理的两部分， 但是可以运用判断来确定答案在数组的哪一边，首先先确定数组的左半边是否是递增的，如果是，再根据目标数字是否落在该区间来决定二分法要舍弃哪一边， 如果不是，根据目标数字是否落在另一半区间里决定二分法要舍弃哪一边。基本上就是先判断是否递增， 在根据情况选区间。

代码：