이진탐색
-
[알고리즘] 이분 탐색(이진 탐색)STUDY/Algorithm 2021. 4. 14. 11:30
이분 탐색(이진 탐색) 이분 탐색은 탐색 범위를 두 부분으로 분할하여 해답을 찾는 방법이다. 이분 탐색을 진행하는 방식을 살펴보자. 1. 이분 탐색을 하고자 할 때는 이미 탐색 대상이 정렬되어있어야 한다. 2. left, right으로 중앙값을 잡아준다. 3. 중앙값과 구하고자하는 값을 비교한다. 4. 비교했을 때, 구하려고 하는 값이 중앙값 보다 큰 경우, left = mid + 1로 두고, 작은 경우는 right = mid - 1로 두고 left > right이 될때까지 계속 반복한다. 이진 탐색의 시간 복잡도 유한 정렬 배열의 크기를 N 배열 내 탐색 값이 없는 최악의 경우 N* 1/2 * 1/2 * 1/2... 범위 내 원소가 하나가 될 때까지 진행되므로 N * (1 / 2)K = 1 -> ..