[탐색(검색) 알고리즘] 파이썬으로 이진 탐색 구현하기 (이진 탐색 알고리즘 Binary search algorithm 구현 방법)

 

이진 탐색 알고리즘 (Binary search algorithm)

파이썬 (Python)으로 탐색 (검색) 알고리즘 (Search algorithm)의 이진 탐색 (Binary search) 코드를구현하는 방법 

1. 이진 탐색 알고리즘 : 글로 써보기
2. 이진 탐색 알고리즘 구현해보기 (도전) - 코드 설명, 유의점
3. 🌟이진 탐색 알고리즘 (정답)🌟 - 이진 탐색 알고리즘 코드, 코드 설명
4. 이진 탐색 알고리즘 실행 과정 출력 코드

 

---

 

1. 이진 탐색 알고리즘 : 글로 써보기

이진 탐색 시에 3개의 포인트가 중요하다. 시작 인덱스, 끝 인덱스, 중간 인덱스

우선 중간 인덱스를 구하고, 이를 타겟 x와 비교한다.

-> 맞으면 이 중간 인덱스를 반환한다.

-> 중간 인덱스보다 타겟 x가 크면, 중간 인덱스를 중심으로 좌측의 배열은 제외한다.

-> 중간 인덱스보다 타겟 x가 작으면, 중간 인덱스를 중심으로 우측의 배열은 제외한다.

중간 인덱스를 다시 구하고, 다시 타겟 x와 비교하는 것을 반복한다.

 

 

---

 

 

2. 이진 탐색 알고리즘 구현해보기 (도전)

def binary_search(x, L):
    low = 0
    high = len(L)
    middle = high // 2
    
    while True : 
        if L[middle] == x :
            return middle
        elif middle <= 0 and L[middle] != x : 
            return None
        elif L[middle] > x :
            middle = middle // 2
        elif L[middle] < x :
            middle += middle // 2
            if middle > high :
                return None

 

코드 설명 :

우선 시작 인덱스와 끝 인덱스를 low와 high로 지정했다. 중간 인덱스도 middle로 지정했다.

 

그리고 원하는 타겟 x를 찾을 때까지 반복해야 하므로 while문을 사용했고, 그 안에서 middle이 x와 같을 때, 더 클 때, 더 작을 때의 경우를 구분하여 middle 값을 다르게 조정하였다.

 

x가 없을 때를 대비하는 코드도 작성해야 하는데, 이 부분에서 고민이 많았다. 원래는 중간 인덱스와 타겟을 비교하는 과정에서 탐색하고자 하는 영역의 인덱스 값이 조정되게 하고자 했는데, middle 값만 변경하면 되어서 조건문마다 middle의 증감을 입력했다. 그러다보니 따로 x가 없었을 때를 대비하는 코드가 필요했다. return을 None으로 지정한 부분이 이에 해당된다. x가 주어진 리스트의 값들보다 작은 경우, 큰 경우 두 가지로 따로 작성했는데, 이 방법 말고도 더 간단히 한 번에 예외 조건을 줄 수 있을 것 같은데 이를 해결하지는 못 했다.

 

1. 시작 인덱스, 끝 인덱스, 중간 인덱스 초기화

2. 반복문 아래에 조건문 작성 : 중간 인덱스와 타겟의 값 비교를 통한 인덱스 반환 혹은 중간 인덱스 값 조정

3. x가 없을 때의 조건 설정

 

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]))

 

위 5개의 테스트 케이스를 실행하면 총 105 step이 실행된다. (탐색 횟수와는 다르다!)

 

 

유의점 : 

1. 시작 인덱스, 끝 인덱스, 중간 인덱스 초기화
2. 반복문 아래에 조건문 작성 : 중간 인덱스와 타겟의 값 비교를 통한 인덱스 반환 혹은 중간 인덱스 값 조정
3. x가 없을 때의 조건 설정

위와 같은 내용을 코드로 구현했다. 정답과 비교하여 유의해야 할 점은 2가지 이다.

1. 중간 인덱스를 반복문 안에서 한 번만 설정하면 더 간단하다.

2. x가 없을 때의 조건을 반복문에서부터 설정하면 더 간단하다.

 

 

---

 

3. 이진 탐색 알고리즘 (정답)

def binary_search(x, L):
    low = 0   
    high = len(L) - 1   
    
    while low <= high:
        middle = (low + high) // 2
        if L[middle] == x:
            return middle
        elif L[middle] > x:
            high = middle - 1
        else:
            low = middle + 1
    return None

코드 설명 : 

처음에 시작 인덱스 low와 끝 인덱스 high를 설정한다. 이 때, 리스트 L의 길이가 n이면 high는 n-1이 되어야 한다. 인덱스가 0부터 시작되기 때문이다.

 

다음으로 반복문을 while로 구현할 건데, 이진 탐색으로 배열을 전부 살펴볼 때까지의 조건을 부여할 것이다. 반복문 내에서 모든 인덱스를 바꿀 것인데, 그렇다면 시작 인덱스가 끝 인덱스와 같거나 큰 숫자가 되는 순간 종료되어야 한다. 따라서 `low <= high`로 조건을 주었다.

 

그리고 그 안에서 중간 인덱스 middle의 값을 지정해줄 것이다. 시작 인덱스와 끝 인덱스의 중간값으로 지정하며, 소수가 아닌 정수여야 하므로 `// 2`를 지정해준다. 그러면 몫만 출력된다. 이진 탐색에서는 배열의 길이가 짝수인 경우 정중앙값이 없는데, 이 때엔 중앙의 왼쪽에 있는 더 작은 값을 middle로 지정해준다.

 

중간 인덱스의 값이 타겟과 같다면? 타겟보다 크다면? 타겟보다 작다면? 이 3가지 각각의 조건에 따라 인덱스를 조정해주어야 한다.

- (if) 같다면 간단하다. 찾고자 하는 답을 찾은 것이다. 코드가 종료된다.

- (elif) 타겟보다 크다면 중간 인덱스보다 작은 좌측의 값들은 필요 없어진다. 끝 인덱스가 지금의 중간 인덱스보다 하나 작은 값으로 설정된다.

- (else) 타겟보다 작다면 중간 인덱스보다 큰 우측의 값들은 필요 없어진다. 시작 인덱스가 지금의 중간 인덱스보다 하나 큰 값으로 설정된다.

 

배열의 모든 요소를 탐색하여 조건문을 빠져나왔는데 원하는 값이 없었다면 아무 것도 반환되지 않는다. 따라서 별도로 이 경우에 None을 리턴하는 코드를 삽입하였다.

 

 

위의 문단들을 정리하면 아래와 같다.

 

1. 시작 인덱스, 끝 인덱스 설정

2. 반복문이 실행되는 조건으로 탐색 횟수를 지정

3. 반복문 내에서 중간 인덱스 설정

4. 반복문 내의 조건문으로 중간 인덱스가 타겟인 경우, 큰 경우, 작은 경우를 설정하여 각각 인덱스를 변경

5. 타겟이 주어진 리스트 내에 없을 경우 반환값 지정

 

 

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]))

위 5개의 테스트 케이스를 실행하면 총 101 step이 실행된다. (탐색 횟수와는 다르다!) 처음에 내가 작성했던 코드보다 4step이 더 적다.

 

 

---

반응형

 

 

4. 이진 탐색 알고리즘 실행 과정 출력 코드

def binary_search(x, L):
    low = 0   
    high = len(L) - 1   
    
    for i in range(len(L)):
        print(f'{i:4}', end='')
    print()
    print((4 * len(L) + 4) * '-')

    while low <= high:
        middle = (low + high) // 2
        
        print()
        if low != high :
            print(' ' * 1 + (low * 4 + 1) * ' ' + '|' + ((middle-low) * 4) * ' ' + '+', ((high - middle) * 4 - 1) * ' ' + '|')
        else :
            print(' ' * 1 + (high * 4 + 1) * ' ' + '|+', '|')
        for i in range(len(L)):
            print(f'{L[i]:4}', end='')
        print()
        print((4 * len(L) + 4) * '-')
        
        if L[middle] == x:
            return middle
        elif L[middle] > x:
            high = middle - 1
        else:
            low = middle + 1
    return None

 

 

 

 

---

 

모든 자료 구조와 알고리즘에 대해 알아보고 싶다면?

🔆 자료 구조와 알고리즘 살펴보기 🔆
https://yoonhwis.tistory.com/135 

🌟 자료구조와 알고리즘 : 기본 개념, 공부 단계