[Python] 이진 탐색

• 정렬된 자료를 반으로 나누어 탐색하는 방법
• 주의점 : 자료는 오름차순으로 정렬된 자료여야 한다.
• 이진트리, 이진탐색은 코딩 인터뷰 단골 문제
• 이진 탐색은 O(log N)의 속도로 검색 가능

 

• 구현을 위한 준비

1. target : 찾고자 하는 값
2. data : 오름차순으로 정렬된 list
3. start : data의 처음 값 인덱스
4. end : data의 마지막 값 인덱스
5. mid : start, end의 중간 인덱스

• 구현개요

1. 배열 전체의 중간 값을 target 값과 비교
2. 중간 값이 target 값보다 큰지, 작은지에 따라 왼쪽, 오른쪽 반 선택
3. 그 부분의 중간 값을 또 target과 비교 (반복)

 

def binary_search(array,target,start,end):
  while start <= end: # 첫 인덱스 값이 마지막 값 인덱스보다 작거나 같다는 가정하에
    mid = (start + end) // 2 # 중간 인덱스 값은 두 합의 절반이고

    if array[mid] == target: # 만약 배열의 중간 값이 타겟 값과 같으면 mid로 리턴
      return mid
    elif array[mid] > target: # 배열의 중간 값이 타겟 값보다 크면 
      end = mid - 1           # 마지막 인덱스 값을 중간 인덱스 값 - 1 로 해서 반복
    else:
      start = mid + 1         # 작으면, 시작 인덱스 값을 중간 + 1로 해서 반복
  return None