[선형탐색과 이진탐색]

선형 탐색이란, 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘입니다.

 

이진 탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 합니다.

정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능합니다.

왜 이 알고리즘의 이름이 ‘이진 탐색’일까요?

1회 비교를 거칠 때마다 탐색 범위가 (대략) 절반으로 줄어들기 때문입니다.

 

 

binary search

def binary_search(element, some_list):
    start = 0
    end = len(some_list)-1

    while (start>=0 and end<len(some_list) and start<=end):
        mid = (start + end) // 2
        if (element == some_list[mid]):
            return mid
        elif (element > some_list[mid]):
            start = mid+1
        elif (element < some_list[mid]):
            end = mid-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
'''

=> 다시 해볼 필요가 있음.

 

* Check Point

- while문 유지조건 

  : 맨 마지막에 원소 두개만 남았을때의 상황 고려. (start<=end)