목록이분 탐색 (1)

beepbeep

LeetCode 33번 - Search in Rotated Sorted Array

문제 배열이 하나 주어집니다. 주어진 배열은 오름차순으로 정렬된 배열을, 특정 인덱스를 기점으로 회전시킨 배열입니다. * 회전 예시 : [0, 1, 2, 3, 4] -> 인덱스2를 기준으로 회전 -> [2, 3, 4, 0, 1] 주어진 값을 배열에서 찾고, 그 때의 인덱스를 반환하세요. 단, 작성한 코드의 시간 복잡도는 반드시 Big-O(logN)이어야 합니다. 살펴보기 주어진 조건( Big-O(logN) )을 만족하려면 선형탐색을 해선 안되고, 최악의 경우 BIg-O(logN)의 시간복잡도를 가지는 탐색법인 이분 탐색을 사용하는 것이 좋을 것 같다. 배열이 회전한 상태이므로 이분탐색에 약간 변형을 주어야 한다... 일단 시작은 기존의 이분탐색과 같다. 1. 배열에서 중간값을 고른다. 2. 중간값이 찾는..
코딩테스트 연습/탐색 2023. 3. 2. 09:51
이전 Prev 1 Next 다음