[파이썬]리스트 검색하기(순차 탐색, 이진 탐색)

10.10 리스트 검색하기(Searching Lists)

- 리스트가 정렬되어있다고 할 때, 이진 검색(binary search)이 순차 검색(linear search)보다 더 효율적으로 요소를 찾을 수 있다.

- 검색은 특정한 요소를 찾는 과정이다. 

- 그래서 리스트 클래스는 검색을 위해 인덱스 메소드(index method)와 요소를 결정하기 위해 in, not in 연산자를 제공한다. 

- 검색은 컴퓨터 프로그래밍에서 일반적인 일이며, 검색을 위한 수 많은 알고리즘들이 존재한다.

- 여기서는 순차 검색(linear search)과 이진 검색(binary search)을 이용한다.

 

 

10.10.1 순차 검색 접근 (The Linear Search Approach)

- 순차 검색 접근법은 키(key)라는 요소를 가지고 순차적으로 리스트의 각 요소들을 비교하는 접근법이다.

- 키(key)가 찾고자 하는 요소와 일치 할 때 까지 수행을 진행하고, 없다면 다 써버릴때 까지 진행한다.

- 만약 매치되었을 경우, 순차 검색은 매칭된 요소의 인덱스를 반환한다.

- 만약 매치가 되지 않았을 경우 -1을 반환한다.

 

*LinearSearch.py

#키와 일치하는 요소를 키를 이용해 찾는 함수
def linearSearch(lst, key):
    for i in range(len(lst)):
        if key == lst[i]:
            return i
 
    return -1
 
lst = [1,4,4,2,5,-3,6,2]
i = linearSearch(lst,4) # Returns 1
j = linearSearch(lst, -4) # Returns -1
k = linearSearch(lst,-3) # Returns 5
 
print("i = ",i, " j = ", j, "k = ", k)

 

- 순차 탐색 함수는 리스트의 각 요소를 하나 씩 키(key)와 비교한다.

- 평균적으로 이 알고리즘은 검색이 완료되기 전에 절반 이상 리스트를 탐색한다.

- 리스트 요소의 수가 커지면 커질 수록 선형 검색 시간은 증가한다. 그래서 큰 리스트에서는 비효율적이다.

 

10.10.2 이진 검색 접근(The Binary Search Approach)

- 이진 검색(binary Search)은 정렬된 리스트의 중간부터 비교해나가는 접근법이다. 즉 리스트를 반으로 나눠 검색한다.

- 이진검색에는 아래와 같은 세가지 경우의 수가 있다.

◆ 만약 키(key)가 리스트의 중간 요소보다 작을 경우, 리스트의 중간 이전까지만 탐색하면 된다.

◆ 만약 키(key)가 리스트의 중간 요소와 일치한다면(찾고자 하는 요소가 중간요소라면), 검색은 끝이 난다.

◆ 만약 키(key)가 리스트의 중간 요소보다 클 경우, 리스트의 중간 이후만 탐색하면 된다.

 

- 탐색중 리스트는 비교가 끝날 때 마다 검색 범위가 절반으로 줄어 든다.

- 첫번째 인덱스와 마지막 인덱스를 나타내는 low와 high 변수가 필요하다. low가 0, high가 n-1이다.

- 중간 인덱스를 나타내는 mid도 필요한데, mid는 (low + high) // 2이다.

- 알고리즘을 차근차근 살펴보자.

 

- 먼저 키(key)와 low 인덱스가 0이고 high 인덱스가 len(lst)-1인 리스트의 중간 요소를 비교한다

- 만약 key < lst[mid] 라면, high 인덱스 값을 mid - 1로 바꾼다.

- 만약 key == lst[mid] 라면, 검색하고자 하는 요소를 찾은것이므로 mid 변수를 반환(return)한다.

- 만약 key > lst[mid] 라면, low 인덱스를 mid + 1로 바꾼다.

- 이 과정을 반복해 key 값을 찾거나, 키값을 못찾았을 때(low > high) 탐색을 종료한다.

 

 

 

*이진 탐색 함수 ver.1

def binarySearch(lst, key):
    low = 0
    high = len(lst) - 1
 
    mid = (low+high) // 2
 
    if key < lst[mid]:
        high = mid - 1
 
    elif key == lst[mid] :
        return mid
 
    else :
        low = mid + 1

 

*이진 탐색 함수 ver.2

def binarySearch(lst, key):
    low = 0
    high = len(lst) - 1
 
    while high >= low:
        mid = (low + high) // 2
 
        if key < lst[mid]:
            high = mid - 1
 
        elif key == lst[mid]:
            return mid
 
        else :
            low = mid + 1
 
    return -1 #not Found

 

- 만약 키(key)와 일치하는 값을 찾지 못했을 경우의 low 값이 key가 삽입된 지점(insertion point)이다.

- 이는 key 값이 위치한 지점을 반환받을 때 유용하다.

- key와 일치하는 값을 찾지 못한 경우, 반환값은 음수이어야 한다.

- 간단하게 -low를 반환하면 되지 않느냐고 생각할 수 있지만, 인덱스가 0일 경우 음수로 표현 할 수 없으므로 -low-1을 반환하는 것이 바람직하다.

- -low-1을 반환하게 코드를 작성하면 키값을 찾지못해는 사실 뿐만 아니라 찾을 때 사용한 key 변수의 삽입지점(insertion point)를 알 수 있다.

 

* 이진 탐색 함수(-low-1 반환)

def binarySeach(lst, key):
    low = 0
    high = len(lst) - 1
 
    while high >= low :
        mid = (low+high) // 2
        if key < lst[mid] :
            high = mid - 1
        elif key == lst[mid]:
            return mid
        else:
            low = mid + 1
 
    return -low-1 

 

참고 문헌 : Introduction to Programming Using Python / Y.DANIEL LIANG

※
본 게시물은 개인적인 용도로 작성된 게시물입니다. 이후 포트폴리오로 사용될 정리 자료이니 불펌과 무단도용은 하지 말아주시고 개인 공부 목적으로만 이용해주시기 바랍니다.

교재 영어 원서를 직접 번역하여 정리한 게시물이므로 일부 오타, 의역이 존재할 수 있습니다. 틀린 부분이 있다면 댓글로 알려주시면 감사하겠습니다. 

※