선형 탐색(Linear Search), 이진 탐색(Binary Search)

선형 탐색(Linear Search)

 

선형탐색은 처음부터 끝까지 순차적으로 탐색해 나가는 방법입니다.

 

파이썬 코드 (Python Code)

def linear_search(element, some_list):
    for i in range(len(some_list)):
        if some_list[i] == element:
            return i
    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]))

 

이진 탐색(Binary Search)

 

정렬된 리스트가 있을 때, 이진 탐색을 할 수 있습니다.

 

1. 리스트에서 중앙 값을 탐색 : (첫 인덱스 + 마지막 인덱스) / 2 = 대략 중앙 인덱스로 리스트의 중앙 값 체크

2. 중앙 값과 찾고자 하는 값을 비교하여 같으면 OK

아니면, 찾는 것보다

크면 찾은 위치부터 큰 값은 제외(반 제외 시킴),

작으면 제일 작은 값부터 탐색한 위치까지 제외

3. 반복해나가면서 탐색

 

이진 탐색(Binary Search)은 반 씩 줄여 나가면서 찾는 방법입니다.

 

파이썬 코드 (Python Code)

def binary_search(element, some_list):
    # 코드를 작성하세요.
    first = 0
    last =  len(some_list) - 1    
    
    
    # for i in range(0, len(some_list)) :
    while first <= last :    
        center = int((first + last) / 2)
        if element == some_list[center] :
            return center
        elif element > some_list[center] :
            first = center + 1
        elif element < some_list[center] :
            last = center - 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]))