[leetcode][33] Search in Rotated Sorted Array
문제 : https://leetcode.com/problems/search-in-rotated-sorted-array/ 오름차순으로 정렬된 중복되지 않은 요소들을 가진 배열이 있다. 이 배열을 어떤 인덱스에서 회전시킨다. 예를 들어, [0, 1, 2, 3, 4,5,6,7]은 [4, 5, 6, 7, 0, 1, 2, 3] 가 될 수도 있다. 회전된 배열이 주어질 때, 이 배열에서 target 값이 어디있는지 인덱스를 찾아라. 없다면 -1을 반환. 단, 시간복잡도는 O(logN) 이어야 한다. 이분 탐색으로 풀었다. 배열 [4 5 6 7 8 0 1] [5 1 2 3 4]로 예를 들어보자. 중간 인덱스를 기준으로 왼쪽과 오른쪽이 있고 이들이 오름차순인지 내림차순인지 구한다. 이 때, 오름차순과 내림차순은 배열을..
2020. 4. 19.