Search in Rotated Sorted Array

Search in Rotated Sorted Array

|| 문제설명 ||

1. 오름차순으로 정렬된 정수배열 nums와 정수 target이 주어진다.

2. 이때 nums는 어떠한 pivot에 의해 회전된 상태이다.

3. 배열에서 target이 발견되면 해당 인덱스 번호를 없다면 -1을 반환하라.

   1 <= nums.length <= 5000
   -10^4 <= nums[i] <= 10^4
   All values of nums are unique.
   nums is guranteed to be rotated at some pivot. 
   -10^4 <= target <= 10^4

   .

• Input

  vector< int>& nums
  int target

• Output

  int

---

|| 문제해결과정 ||

O(n) : 전체 확인

O(logn) : 이분탐색

- nums[0] = pivot
- pivot보다 	작으면 뒤에서부터 큰수 나오기 전까지
		크면 앞에서부터 작은수 나오기 전까지

---

|| 코드 ||

[2020.11.01] 성공

- O(n)

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for(int i=0; i<nums.size(); i++) {
            if(nums[i] == target) {
                return i;
            }
        }
        return -1;
    }
};

---