이분탐색 Binary Search

이분탐색

어떠한 특정 데이터를 찾기위해 "정렬된" 배열에서 탐색하고, 범위를 절반씩 줄여가면서 찾는 탐색 방법이다

300이라는 숫자가 배열이 있는지 없는지 확인해본다고 해보자.
위와 같이 배열이 주어질 때, 배열의 시작과 끝 부분을 정한다.

#python 

list = [ 1,9,12,31,99,120,191,300,309]

start = 0
end = len(list) - 1

그리고 "(시작 + 끝) / 2" 을 계산하여, 중간 인덱스를 찾아준다.
위의 예로서는 "0 + 8 / 2" 니까 중간 인덱스는 4가 된다.

mid = ( start + end ) // 2

그러면 배열의 4번째 값인 99 보다 찾고싶은 수인 N이 작은지 큰지 아니면 같은지 확인한다.

if N < list[mid] :  
	end = mid -1
  
elif list[mid] < N :
	start = mid + 1

else :
	result = mid
    break

그리고 이 과정을 반복하며 300 있는지 없는지 확인하면 된다.

while start >= end :
  mid = ( start + end ) // 2

  if N < list[mid] :  
      end = mid -1

  elif list[mid] < N :
      start = mid + 1

  else :
      result = mid
      break

만약 start가 end 값을 넘어간다면 배열에는 300은 없을 것이고, 있다면 else 문에서 처리되어 값을 찾을 수 있다.

그러면 왜 많은 알고리즘 중에서 이분탐색을 사용할까?

이분탐색의 장점은 아주 큰~~~ 배열이 주어지더라도, 탐색시간을 적게 가져 갈 수 있다는 것이다.
하지만 정렬된 배열에서만 가능한 알고리즘이기 때문에, 정렬이 되어있지 않는 배열이 주어진다면,
배열을 정렬시키는 시간까지 생각하여 이분탐색을 사용했을 때 효과적인지 확인해야 한다.