이진탐색 (Python)

개념

이진 탐색이란 정렬되어있는 데이터 집합을 이분화하여 탐색하는 방법이다. 이때 정렬된 데이터가 키 포인트인데 정렬이 되어있지 않다면 쓸 수 없다. start, end, mid를 이용하여 target을 탐색을 하는데 여기서 mid는 (start + end) // 2 한 값 즉 중간값이다. 이제 3가지 경우가 존재하는데 각각의 경우는 다음과 같다.

 

1. array[mid] == target 

2. array[mid] > target 

3. array[mid] < target

 

1번의 경우 단순하게 해당 mid값을 return 해주면 된다.

2번의 경우 중간값에 해당하는 값이 찾고자 하는 값 보다 크기 때문에 중간값 좌측의 구간만 다시 탐색을 해주면 된다. 따라서 end = mid - 1

3번의 경우 중간값에 해당하는 값이 찾고자 하는 값 보다 작기 때문에 중간값 우측의 구간만 다시 탐색을 해주면 된다.

따라서 start = mid + 1

구현은 재귀의 경우가 반복문의 경우보다 느리다고 알고 있기 때문에 더 효율적인 반복문의 형태로 구현을 한다.

---

소스코드

 

def binary_search(array, target, start, end):
  while start <= end:
    mid = (start + end) // 2
    if array[mid] == target:
      return mid
    elif array[mid] > target:
      end = mid - 1
    else:
      start = mid + 1
  return -1 # target을 array에서 찾지 못한 경우
 
n, x = map(int, input().split())
data = list(map(int, input().split()))
result = binary_search(data, x, 0, n-1)
if result == -1:
  print("찾으시는 숫자가 존재하지 않습니다")
else:
  print(result + 1)