python 기본 검색 알고리즘 - 선형검색과 이진검색

python 문법을 통한 검색 알고리즘 선형 검색과 이진 검색에 대해서 알아보자. 선형 검색은 가장 기본적인 알고리즘으로 맨 앞부터 순수대로 검색하는 알고리즘이고, 이진 검색은 검색할 데이터의 기준값을 부여하여 선형 검색보다 빠르게 검색할 수 있는 알고리즘이다.

 

 

 

선형 검색

가장 기본적인 검색 알고리즘으로 원하는 값을 찾을때까지 맨 앞부터 순서대로 검색하는 알고리즘이다. 선형 검색은 검색 성공과 검색 실패 의 두 가지 종료 조건으로 나뉜다.  

# 선형검색
def line_search(list, key):
    for i in range(len(list)):
        # 검색 성공
        if(list[i] == key):
            return list[i]
    else:
        # 검색 실패
        return 'None'


if __name__ == '__main__':
    list = ['가', '나', '다', '라', '마', ]
    key = '마'

print(line_search(list, key))

 

선형 검색의 경우 반복하는 횟수마다 성공과 실패의 두가지 조건을 확인해야 하기 때문에 검색하는 항목이 늘어날수록 검색에 발생되는 비용이 늘어날 수밖에 없다. 

 

그래서, 검색해야하는 대상을 배열의 맨 마지막에 넣어, 실패 조건을 판단하는 횟수를 줄이는 보초법을 이용할 수 있다.

# 선형검색 - 보초법
def line_search(list, key):

    # 배열 마지막에 key 등록
    list.append(key)

    for i in range(len(list)):
        # 검색 성공
        if(list[i] == key):
            break

    return 'None' if (i+1) == len(list) else list[i]


if __name__ == '__main__':
    list = ['가', '나', '다', '라', '마', ]
    key = '나'

    print(line_search(list, key))

 

이진 검색

검색할 전체 범위의 시작 값, 중앙 값, 마지막 값을 기본으로 검색할 데이터를 찾는 알고리즘이다. 선형 검색보다 빠르며, 일정한 규칙을 갖고 있는 데이터로 그룹에서 사용 가능한데, 데이터 그룹은 오름차순 또는 내림차순으로 정렬된 상태여야 한다.

 

• 기본값 
  시작 : start =0
  중앙 :  center = (start+end)/2
  마지막 : end = n- 1
  
  
• 알고리즘 
  • 검색 키값 > 가운데 값
    중앙값에서 오른쪽으로 한칸 이동하여, 새로운 범위의 시작값(start)을 재설정합니다.
  • 검색 키값 < 가운데 값
    중앙값에서 왼쪽으로 한칸 이동하여, 새로운 범위의 마지막값(end)을 설정합니다.

 

 

# 이진검색
def binary_search(list, key) -> int:
    start = 0
    end = len(list)-1

    for i in range(len(list)):
        center = int((start+end)/2)

        if(key == list[center]):
            return center
        elif(key > list[center]):
            start = center+1
        else:
            end = center-1

        if start > end:
            break


if __name__ == '__main__':
    key = 7
    list = [1, 2, 3, 4, 5, 6, 7, 8,
            9, 10, 11, ]
    print(f'list[{binary_search(list, key)}]')