62. Search in Rotated Sorted Arr
2019-06-04 本文已影响0人
鸭蛋蛋_8441
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
思路：
看到题目要求就猜到用二分法， 但是这个题的难点在于无法把数据分为合理的两部分， 但是可以运用判断来确定答案在数组的哪一边，首先先确定数组的左半边是否是递增的，如果是，再根据目标数字是否落在该区间来决定二分法要舍弃哪一边， 如果不是，根据目标数字是否落在另一半区间里决定二分法要舍弃哪一边。基本上就是先判断是否递增， 在根据情况选区间。
代码：
