Python side project 04 : binary search (이진 탐색)

 

이틀에 걸쳐서 이진 탐색을 했었다. 

처음에 왜 이렇게 하는지 이해를 하지못해서..

또 사소한 데 코드를 잘못쳐서.. 

디버깅하고 에러를 찾느냐 시간을 많이 사용했던 프로젝트였다.

 

우선, 이진 탐색이란,

탐색할 자료를 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법이다.

 

탐색 방법은 두가지가 있는데 위에서 설명한 이진 탐색과 순차 탐색 두가지이다. 

아래의 이미지를 참고하면 훨씬 이해하기가 쉬울 것 같다.

이진 탐색의 이해 (순차 탐색과 비교하며 이해하기)

이미지 출처 : https://www.fun-coding.org/Chapter16-binarysearch.html

 

두번째, 순차탐색의 경우에는 타겟을 찾는데 많은 시간이 걸린다는 단점이 있다.

하지만 이진 탐색의 경우에는 분할 정복 알고리즘을 사용하여 문제를 해결 가능할때까지

쪼개서 순차 탐색보다 빠르게 문제를 분할하여 답을 찾아내는 방식이다.

 

이를 활용하여 아래 코드를 만들었다.

 

import random
import sys  # 중간에 코드를 점검하기 위한 sys.exit(0) 을 써주기 위해 사용

def binary_search(lists, first, last, target):

    if last >= first:
        mid = (last + first) // 2

        if lists[mid] == target:
            return mid
        elif lists[mid] > target:
            return binary_search(lists, first, mid-1, target)
        else:
            return binary_search(lists, mid+1, last, target)
    else:
        return -1


# test method

lists = [i for i in range(0,10)]
random.shuffle(lists)
print(lists)

target = 8
result = binary_search(lists,0,len(lists),target)

if result != -1:
    print('element is at index', str(result))
else:
    print("element is not in lists")

프로젝트 고려사항

1. first 와 last 에 올바른 숫자가 들어가야 한다.

- 간혹 이 부분에서 헷갈려서 숫자를 잘못 쓰는 경우가 있는데, 이를 방지하기 위해 

   last 와 first 의 크기를 비교하는 이중 if 문을 작성하여 이를 사전에 방지하고자 했다.

 

2. 경우의 수는 3가지이다.

첫번째 if 를 통과하면 우리가 고려할 수 있는 경우의 수는 총 3가지이다.

 

- 우선, lists[mid] 와 target 이 같은 경우

- target 보다 큰 경우

- 마지막 target 보다 작은 경우

 

3. 숫자가 순차적으로 나오지 않더라도 위 알고리즘이 잘 작동되어야 한다.

- 인덱싱을 기준으로 했기에 문제는 없지만, 잘 작동되는지 체크하기 위해 shuffle( ) 를 사용했다.

 

 

결과물은 아래와 같다.

 

참고링크

- 위 코드에 사용한 random.shuffle 에 대한 설명

https://hashcode.co.kr/questions/648/%EB%A6%AC%EC%8A%A4%ED%8A%B8%EC%9D%98-%EC%9B%90%EC%86%8C%EB%A5%BC-%EB%9E%9C%EB%8D%A4%EC%9C%BC%EB%A1%9C-%EC%84%9E%EB%8A%94-%EB%B0%A9%EB%B2%95

리스트의 원소를 랜덤으로 섞는 방법

- 이진 탐색에 대한 더욱 자세한 설명

https://www.fun-coding.org/Chapter16-binarysearch.html

파이썬과 컴퓨터 사이언스(기본 알고리즘): 이진 탐색 (Binary Search) - 잔재미코딩