[leetcode]162. find-peak-element

📃문제 설명

리스트에서 가자 높은 값의 인덱스를 반환하는 문제이다.
시간 복잡도는 o(logN)을 만족하도록 작성해야한다.

🖊 풀이1

시간 복잡도를 고려하지 않고, 가장 먼저 떠오른 방법이다.
파이썬 리스트의 내장 함수인 max와 index는 결국 for문을 돌기 때문에
시간 복잡도는 O(n)이다.

🖊 풀이2

시간 복잡도를 만족시키려면 리스트를 모두 순회하는 것을 피해야한다.
그러기 위해서 우선 리스트의 중간에 위치한 데이터를 이용하여
앞, 뒤의 데이터와 비교하면서 최대값의 인덱스를 반환해보자 >>> 이진 탐색

이진 탐색은 탐색 범위를 계속 절반으로 줄여나가는 방법이기 때문에
시간 복잡도 O(logN)을 만족한다.
하지만 이진탐색은 정렬된 데이터에서 사용되는 방법이다.

❓ 왜 정렬되지 않은 데이터에서 이진 탐색으로 푸는 방법이 가능한가?
이 문제는 peak point를 찾는 문제이다. peak point를 기준으로 데이터를 나눠보면
그룹별로 정렬이 되어 있는 것을 볼 수 있다. (오름차순 or 내림차순)
그룹 별 정렬된 데이터 속에서 이진 탐색을 사용한 것으로 보자