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

º [개념]

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목푯값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

 

º [high와 loew를 지정한] 의사 코드

binarySearch(A[0..N-1], value) {//k
  low = 0
  high = N - 1
  while (low <= high) {
      mid = (low + high) / 2
      if (A[mid] > value)
          high = mid - 1
      else if (A[mid] < value)
          low = mid + 1
      else
          return mid // found k
  }
  return -1 // not found k
}

 

º [파이썬] 재귀 함수 코드

def binarySearch(array, value, low, high):
	if low > high:
		return False
	mid = (low+high) // 2
	if array[mid] > value:
		return binarySearch(array, value, low, mid-1)
	elif array[mid] < value:
		return binarySearch(array, value, mid+1, high)
	else:
		return mid

 

º [시간 복잡도]

참고 자료

  N개 크기의 배열에서 단계가 하나씩 지나감에 따라 배열의 크기가 반으로 줄어든다. 위의 그림처럼 맨 처음에 17개에서 7을 찾고 있다.

중간 값 : 14 -> 작다 -> 8개

중간 값 : 6 -> 크다 -> 4개

중간 값 : 8 -> 작다 -> 1개 

 

이런 식으로 빠르게 찾을 수 있다. 탐색이 3회 수행돼서 시간 복잡도는 3이다.

일반화하여 생각해보면 N개의 크기 배열을 이진 탐색하면 N, N/2, N/4, N/8... 1로 실행된다. 여기서 탐색 회수는 K 이것을 N에 대해 나타낸다면 1에 2를 K번 곱하면 == N, 즉 2^K = N ( K = log 2 N )이 된다. 

즉, 시간 복잡도는 O(log N )이 된다. 

 

º [참고사이트]

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%EA%B2%80%EC%83%89_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

이진 검색 알고리즘 - 위키백과, 우리 모두의 백과사전

https://cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제