[파이썬 기초] 알고리즘의 개념 / 코딩 연습 - 예제3(이진 탐색 알고리즘)

# 이진 탐색 알고리즘(binary search algorithm) : 정렬된 리스트를 전제로, 탐색 범위를 절반으로 줄여 가며 탐색을 진행하는 알고리즘

 

코드잇 예제풀이(이진탐색 알고리즘 문제) : 파라미터로 탐색할 값 element와 리스트 some_list를 받는 함수 binary_search를 정의하여 그 위치(인덱스) 혹은 None를 리턴

 

* 이진 탐색 알고리즘의 진행 순서(예시)

[1, 2, 3, 5, 8, 13, 21, 34, 55]에서 3을 찾는 경우의 알고리즘의 진행 방식은 다음과 같다.

 

시도 1

리스트의 첫 번째 인덱스(원소의 위치)와 마지막 인덱스의 값을 합하여 2로 나눈 후, 그 몫을 중간 인덱스로 지정함(인덱스는 소수점이 될 수 없으므로 나눈 몫을 중간 인덱스로 지정). 그 중간 인덱스에 해당하는 값이 3인지 확인한다.

→ 첫 번째 시도에서 중간 인덱스는 (0+8) // 2 = 4가 되고, 인덱스 4에 해당하는 원소는 8인데, 8은 3보다 크다. 리스트가 정렬되어 있기 때문에, 인덱스 4~8은 두번째 탐색 범위에서 제외시킬 수 있다.

 

시도 2

두 번째 시도에서 중간 인덱스는 (0+3) // 2 = 1이 되고, 인덱스 1에 해당하는 원소는 2인데, 2는 3보다 작다. 리스트 0~1은 세 번째 탐색 범위에서 제외시킬 수 있다.

 

시도 3

세 번째 탐색 범위의 중간 인덱스는 (2+3) // 2 = 2가 되고, 인덱스 2에 해당하는 원소는 3인데, 찾고자 하는 원소와 일치한다. 이제 인덱스 2를 리턴하고 알고리즘을 종료한다.

 

Hint 1 : 최초 탐색 범위 설정 : 인덱스 0부터 인덱스 len(some_list) - 1까지 → 시작 인덱스와 종료 인덱스를 설정함으로써 탐색 범위 설정 → start_index와 end_index 설정

 

Hint 2 : 설정된 최초 탐색 범위 내에서 while 조건 반복문 설정 → 시작 인덱스와 종료 인덱스가 엇갈리기 전까지 반복.시작 인덱스: 1) 현재 탐색 범위에서의 중간 인덱스에 해당하는 값이 element면, 그 중간 인덱스 값을 리턴한다 . 2) 그렇지 않으면, 탐색 범위를 줄인다. → 1) midpoint 설정 2) 중간 인덱스 값이 element보다 작을 때와 클 때를 나누어 설정

 

Hint 3 : 조건문 중 elif와 else를 사용하여 시작 인덱스와 종료 인덱스 범위를 midpoint를 기준으로 조정해 나간다. → 중간 인덱스 값이 element보다 크다면, 종료 인덱스를 midpoint - 1로 지정 (예시에서 8이 3보다 크다면 두 번째 탐색 시도에서의 종료 인덱스는 5) / 중간 인덱스 값이 element 보다 작다면, 시작 인덱스를 midpoint  + 1로 지정

 

====================================================================  

 

 def binary_search(element, some_list):

      start_index = 0

      end_index = len(some_list) - 1

 

      while start_index <= end_index:

           midpoint = (start_index + end_index) // 2

           if some_list[midpoint] == element:

               return midpoint

           elif some_list[midpoint] > element:

               end_index = midpoint - 1

           else:

               start_index = midpoint + 1

 

      return None

 

print(binary_search(2, [2, 3, 5, 7, 11]))
print(binary_search(0, [2, 3, 5, 7, 11]))
print(binary_search(5, [2, 3, 5, 7, 11]))
print(binary_search(3, [2, 3, 5, 7, 11]))
print(binary_search(11, [2, 3, 5, 7, 11]))

 

0

None

2

1

4