[Python 자료구조] 이진검색

이진검색 조건문 코드 개선 : [Python 자료구조] 이진검색 코드 개선 :: 코딩 연구소 (tistory.com)

 

💡 이진 검색

 

이진 검색 알고리즘은 이미 정렬된 상태의 배열에서 선형 검색보다 빠르게 검색을 수행한다.

규칙은 검색하려는 값이 중앙 값을 기준으로 작은지 큰지를 판별하는 것이다.

• 오름차순으로 정렬된 리스트에서 특정값의 위치를 찾는 알고리즘
• 처음 중간의 임의 값을 선택하여, 그 값의 크고 작음을 비교

 

[ 1, 2, 3, 4, 5, 6, 7, 8, 9 ] 까지 정렬된 배열이다.

검색 범위를 중앙에서 왼쪽으로 좁힌다. 

 

오른쪽은 무시해도 된다.

내가 찾고자 하는 값이 중앙 값 보다 작기 때문에, 같은 패턴을 반복하여 반씩 줄여 간다.

 

검색 범위를 중앙에서 왼쪽으로 좁히면서, 찾고자 하는 값을 찾을 수 있다.

 

파이썬 코드로 확인해보자.

 

💡 코드

 

def binarySearch(element, arr):
    
    ret = -1 
    first = 0 
    last = len(arr) -1 
    
    while first <= last: 

        mid = (first + last) // 2 
        
        if arr[mid] == element:
            ret = mid
            return ret   
        
        elif arr[mid] > element:
            last = mid - 1
            
        elif arr[mid] < element:
            first = mid + 1
            
    return ret
        
arr = [1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024]
resultSuccess = binarySearch(64, arr)
resultFailed = binarySearch(54, arr)

print ("resultSuccess : {}".format(resultSuccess))
print ("resultFailed : {}".format(resultFailed))

 

ret 는 return 반환 값이다. 

first 는 검색 범위 맨 앞 원소의 인덱스이며, last 는 검색 범위 맨 끝 원소의 인덱스이다.

mid 는 중앙 원소의 인덱스로 arr[mid] 번째가 element 와 값이 같을 경우 중앙 원소 인덱스를 반환하고, 

element 보다 큰 경우 인덱스 -1 을 한다. 

반대로, 중앙 원소 인덱스가 element 보다 작은 경우 인덱스 +1 을 진행하며, 찾고자 하는 값이 없는 경우에는 -1 을 반환 한다.