[알고리즘] 선형탐색과 이진탐색

선형탐색과 이진탐색

1. 탐색

• 저장된 정보들 중에서 원하는 값을 찾는 것

2. 선형탐색 알고리즘(순차검색, Linear search algorithm)

• 찾고자 하는 값을 리스트의 맨 앞에서부터 끝까지 차례대로 찾아 나가는 방식
• 장점: 검색 방법 중 가장 단순하여 구현이 쉽고 정렬되지 않은 리스트에서도 사용할 수 있음
• 단점: 검색할 리스트의 길이가 길면 비효율적
• 예

def linear_search(element, some_list):
    for i in range(len(some_list)):
        if some_list[i] == element:
            return i
        else:
            continue
    return None

print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))

실행결과

0
None
2
1
4

3. 이진탐색 알고리즘(이진검색, Binary search algorithm)

• 오름차순으로 정렬되어있는 리스트에서 특정한 값을 찾을 때, 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식
• 장점: 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠름
• 단점: 정렬된 리스트에만 사용할 수 있음
• 예

def binary_search(element, some_list):
    start_index = 0
    end_index = len(some_list) - 1
    
    while start_index <= end_index:
        midpoint = (start_index + end_index) // 2
        if some_list[midpoint] == element:
            return midpoint
        elif some_list[midpoint] > element:
            end_index = midpoint - 1
        else:
            start_index = midpoint + 1
    return None

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

실행결과

0
None
2
1
4

• 참고: 위키백과, 코드잇