[Algorithm] Binary Search (이진탐색/이분탐색)

gunny·2023년 5월 8일

Binary Search algorithm 알고리즘 이분탐색 이진탐색

Algorithm

목록 보기

1/7

Algorithm - Binary Search

(1) Binary Search Algorithm 정의

Binary Search(이분탐색/이진탐색) : 정렬되어 있는 배열에서 탐색 범위를 줄여나가면서, '특정한 값'을 찾아내는 알고리즘

(2) Binary Search Algorithm 동작 방식

배열의 중간에 있는 임의의 값(mid)을 선택하고, 찾고자 하는 target의 값과 비교하는데,
target이 mid 보다 작으면 mid 기준 좌측의 데이터를 대상으로, target이 mid 보다 크면 mid 기준 우측을 대상으로 다시 탐색하는 방법이고, target을 찾을 때 까지 해당 과정을 반복한다.
그렇기 때문에 Binary Search 는 반드시 '정렬된' 배열에서 사용한다.

(3) Binary Search 예시

오름차순으로 정렬된 배열 A가 있을 때, 43 을 binary Search로 찾기
A = {17, 28, 43, 67, 88, 92, 100}

(1) 가운데에 위치한 `67` 을 mid로 선택 하고 target인 `43` 과 비교함
 =>  mid > target (67>43)이므로, `43`은 `67` 보다 좌측에 위치하고 있음

(2) `67` 기준으로 좌측의 배열의 값 {17,28,43} 에서, 
가운데에 위치한 `28` 을 선택하고 target인 `43` 과 비교함
 => mid < target (28<43) 이므로, `28` 보다 우측에 위치하고 있음

(3) `28`의 우측의 배열은 {43} 으로, taget과 mid의 값이 서로 일치함

Binary Search에서의 탐색의 종료조건은 '원하는 값을 찾으면 종료된다.
운이 좋게 처음에 찾을 수도 있지만, 계속해서 탐색하면서 찾아야 할 경우도 있다.
또한, 원하는 값이 배열에 존재하지 않는 경우가 있을 수 있다.

위와 같은 예시로 오름차순으로 정렬된 배열 A가 있을때 40을 찾는 경우,

(1) 가운데 위치한 `67`을 mid로 선택하고 target 인 `40`과 비교한다.
  위와 동일하게 mid > target (67>40) 이므로, `67` 보다 좌측으로 배열을 재설정한다.

(2) `67` 기준으로 좌측의 배열 값 {17,28,43} 에서 가운데 위치한 `28`을 선택하고,
 target인 `40`과 비교했을 때 mid < target(28<40) 이므로, 28보다 우측에 위치한다.

(3) 이때 남은 배열인 {43}은 target `40` 보다 작아서, 
배열의 좌측을 탐색해야 하지만 더이상 남은 배열이 없기 때문에 탐색을 종료한다.

즉, 이진 탐색의 종료 조건은 [1] 검색을 성공 할 경우 [2] 검색을 실패할 경우(더 이상 검색할 범위가 없을 때) 이다.

(4) Binary Search 구현

= Binary Search 는 [1] 반복문이용 [2] 재귀 로 구현 가능하다.

[1] 반복문 이용

def binarySearch(arr, target):
	start, end = 0,0
	while start<=end:
      mid = (start+end)//2

      if arr[mid] == target:
          return mid
      elif arr[mid] < target:
          start = mid+1
      else:
          end = mid-1
          
      return -1

[2] 재귀 함수 이용

def binarySearch_rec(arr, target, start, end):
		if start > end:
        	return -1
            
        mid = (start+end)//2
        
        if arr[mid] == target:
        	return mid
            
       elif arr[mid] < target:
      		return binarySearch_rec(arr, target, mid+1, end)
       else:
       		return binarySearch_rec(arr, target, start, mid+1)

(5) Binary Search 시간 복잡도

Binary Search의 탐색 시간 복잡도 및 빅오(Big-O Notation)
위에서 사용했던 배열 A = {17, 28, 43, 67, 88, 92, 100} 에서 처음 원소의 개수가 8개에서 4,2,1 . . .
점점 반으로 줄어드는 걸 확인 가능한데, 위의 경우 n=8 에서 탐색이 3회 수행되어 시간복잡도는 3이다.
이를 일반화 한다면, n, n/2, n/4, n/8 . . . 으로 실행된 탐색 횟수가
시간복잡도이므로 복잡도를 k라고 했을 때,2^k = N, K = log2N 으로 시간 복잡도는 O(logN) 이다.