[알고리즘] 이분 탐색(이진 탐색)

이분 탐색(이진 탐색)

이분 탐색은 탐색 범위를 두 부분으로 분할하여 해답을 찾는 방법이다.

이분 탐색을 진행하는 방식을 살펴보자.

 

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 -> K = log2N

 

따라서 이진 탐색의 시간 복잡도는

O(log2N)

 

---

Reference

velog.io/@djh20/JAVA%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89

[JAVA][알고리즘] 이진 탐색(이분 탐색)

 

wootool.tistory.com/62

[알고리즘] 이분 탐색