rotated Array Search with O(log n) - javascript
어떤 정렬된 array가 주어졌을 때, array는 오른쪽 혹은 왼쪽으로 rotate 될 수 있다. ex) sorted array [0, 1, 2, 3, 4, 5, 6, 7] => rotated array [4, 5, 6, 7, 0, 1, 2, 3] rotated array 내에서 target이 되는 숫자를 찾으려면 어떻게 해야 효율적으로 할 수 있을까? 주어진 array의 길이를 n이라고 하였을 때, O(n)이 아닌 O(log n)의 복잡도로 해당하는 숫자와 일치하는 자리의 index를 반환하여라. 해당하는 숫자가 array 내에 없을 경우는 null을 반환하여라. For instance: rotatedArraySearch([4, 5, 6, 0, 1, 2, 3], 2) === 5 rotatedArray..
Programming/Algorithm
2019. 10. 7. 15:43
