알고리즘-이진탐색(Binary Search)

정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제이며 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘.

 

이진 탐색 알고리즘이란 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만

탐색하도록 제한하여 원하는 값을 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고,

없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.

 

이진 탐색은 정렬된 리스트에만 사용할 수 있다는 단점이 있음,대신 검색이 반복되면서 범위가 절반으로 줄어들기 때문에

속도가 빠르다는 단점이 있다.

 

동작방식

1. 배열의 중간 값을 가져온다.

 

2. 중간 값과 검색 값을 비교한다

 

2.1  중간 값 과 검색값이 같다  =  검색 종료  (mid = key)

 

2.2 중간 값 보다 검색값이 크다 >> 중간값 기준 배열 오른쪽 구간을 탐색 ( mid < key)

 

2.3 중간 값보다 검색값이 작다 >> 중간값 기준 배열 왼쪽 구간을 탐색 (mid > key)

 

3. 반복을 통해 값을 찾거나 간격이 없을때 까지 반복 한다.

 

 

예시

이진 탐색 사용해 key = 32 값을 찾는 과정. 

 

1. 배열의 중간 값을 가져온다.

 

mid  = low + (high - low) / 2
          = 0 + (9-0)/2
          = 4

2. 중간 값과 검색 값을 비교한다

 A [4] < key 이므로 배열의 오른쪽 구간을 검색 범위로 정합니다.

 

 low = mid + 1
        = 4 + 1
        = 5

3. 중간 값을 결정한다.

mid = 5+ (9-5)/2
         = 7

4. 중간 값과 검색 값을 비교합니다.

A [7] > key 이므로 배열의 왼쪽 구간을 탐색 범위로 정합니다.

high = mid -1
          = 7 - 1
          = 6

5. 중간 값을 결정합니다.

mid = 5 + (6-5)/2
         = 5

6. 중간 값과 검색 값을 비교합니다.

A [5] = key 이므로 탐색을 종료합니다.

 

 

종료 조건

이진 탐색의 종료조건에는 두가지가 있다. 

1. 검색을 성공한 경우 

검색값 = 값      mid ==key

검색 성공

 

2.검색 실패한 경우

검색 할 범위가 없는 경우

검색 실패

 

 

시간 복잡도(Time complexity)

---

Operation	Best	Average	Worst
Search	O(1)	Θ(log n)	O(log n)

*n = 데이터 수

 

배열의 크기를 N이라고 한다면, 첫 시행 후에는 반이 버려져서 탐색 횟수는 N / 2

 

두 번째 시행 후에는 N / 4 가 될 것이고, k번째 시행 후에는 (1 / 2)k * N

 

결국, 최악의 경우에는 배열의 사이즈가 1이 될 때까지 반으로 쪼개는 것이므로 (1 / 2)k * N = 1이고,  양변에 로그를 취하여 정리하면, log2N이 되는 것을 알 수 있습니다.

 

따라서, 이진 탐색의 시간 복잡도는 O(logN) 입니다.

 

 

 

 

 

Reference
https://namu.wiki/w/%EC%9D%B4%EC%A7%84%20%ED%83%90%EC%83%89

https://yoongrammer.tistory.com/75