Leetcode 33. Search in Rotated Sorted Array - Python
Leetcode 33 문제 보기 문제 이해하기 오름차순으로 정렬된 어떤 정수의 리스트 nums가 특정 값을 기준으로 회전되었다. 예를 들어 [1,2,3,4]가 3을 기준으로 회전되면 [3,4,1,2]가 된다. 어떤 정수 target이 주어질 때, 해당 target이 nums안에 존재하는지 판단하고 만약 존재한다면 그 숫자의 nums내 index값을 반환하고, 존재하지 않는다면 -1을 반환하라. 단, 알고리즘은 O(logn)의 시간복잡도를 가져야 한다. 아이디어 구상 단순히 target이 nums에 있는지 알기위해서는 리스트를 순차적으로 탐색하면서 있는지 없는지 판단하면 될 것이다. 그러나 이는 O(n)의 시간복잡도를 가진다. 때문에 O(logn)의 시간복잡도를 가지기 위해서는 결국 Binary Searc..
2022.07.25