[LeetCode] 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.

Your algorithm's runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1

 

Approach

O(log n)만에 풀어야해서 무식하게 찾으면 안되고

우선 array에서 가장 작은 원소의 index를 이분탐색으로 찾고

이를 바탕으로 찾고자 하는 target을 다시 이분탐색으로 찾는다.

target을 찾을때 0 ~ lowest-1 구간에 있는지, lowest ~ nums.size()-1 구간에 있는지를 판단하는게 포인트

 

Code

https://github.com/chi3236/algorithm/blob/master/LeetCode_SearchInRotatedSortedArray.cpp 

chi3236/algorithm