이진탐색
-
[알고리즘] 이진 탐색개발/자료구조와 알고리즘 2022. 3. 4. 17:56
이진 탐색 (이분 탐색, Binary Search) 이진 탐색 트리와 같이 정렬된 리스트에서 탐색 범위를 두 부분으로 나누어 특정 값을 찾는 방식 앞이나 뒤에서부터 순서대로 원하는 값을 찾는 순차 탐색보다 훨씬 빠르다. 순차 탐색은 $O(N)$의 시간 복잡도를 가지나, 이진 탐색은 $O(logN)$의 속도를 가진다. 빠르기 때문에 효율성을 따져서 무언가를 찾는 문제에서 생각해 볼법하다. 알고리즘 우선 정렬된 리스트에서 최소값의 인덱스를 left, 최대값의 인덱스를 right로 둔다. left와 right를 통해 mid를 만들어준다. mid와 찾는 값$x$ 비교 mid가 더 큰 경우 left = mid+1, mid가 더 작은 경우 right = mid-1 2, 3, 4번을 left>right가 될 때까지 ..