[알고리즘] 이진검색, Binary Search

이진 검색이란

이진 검색이란, 검색 알고리즘 중 하나로서, 매 step마다 리스트의 중간 지점(m)을 기준으로, 찾는 값(x)의 위치를 찾아내는 알고리즘이다.

예

8개의 element가 들어있는 오름차순 리스트 A가 존재한다.
A = { 3, 6, 9, 12, 15, 18, 21, 24}

18이라는 값을 찾는다고 하였을 때,

1. 리스트 A를 반으로 나누어 찾는 값이 기준선 뒤에 존재하는 지 확인한다.
{3 6 9 12 | 15 18 21 24}

2. 기준선 뒤의 값 = 15 < 18 이므로,
앞서 나눠진 두개의 리스트( {3 6 9 12}와 {15 18 21 24} ) 중, 뒤쪽의 리스트 {15 18 21 24} 를 반으로 나누어 다시 확인한다.
{15 18 | 21 24}

3. 기준선 뒤의 값 = 21 > 18 이므로,
앞서 나눠진 두개의 리스트( {15 18}와 {21 24} ) 중, 뒤쪽의 리스트 { 15 18 } 를 반으로 나누어 다시 확인한다. {15 | 18}

4. 기준선 뒤를 체크했더니 찾는 값인 18이 존재!!

위와 같은 방식으로 Binary Search가 이루어진다.
아래는 각각 이를 pseudocode(스도코드)와 파이썬으로 표현한 것이다.

수도코드

Python

listA = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32]

start = 0 #검색 리스트의 왼쪽 시작점
end = len(listA)-1 #검색 리스트의 오른쪽 시작점 # 15
x = 32 # 찾는 값

while (start <= end):
  m = (start+end)//2
  print(listA[start:end+1])

  if x>listA[m]:
    start = m+1 

  elif listA[m] == x:
    location = m
    break

  else:
    end = m -1

print(location)

---

What is Binary Search

Basic idea of Binary Search : On each step, look at the middle element of the remaining list to eliminate half of it.
(Assume the input is a list of items in increasing order.)