3. Python - Array 배열 이진 탐색 구현

리스트 - 이진 탐색 알고리즘

이진 탐색 알고리즘

이진 탐색은 데이터가 정렬이 되어있어야만 의미가 있어요. 당연하겠지만 정렬이 되어있지 않다면 절대 쓰면 안되는 것입니당.

이진 탐색이라는 것은 예를 들어, 배열이

list1 = [1,3,5,6,7,8,24,43,55,67]

이라면 24를 찾게 될 때 전체 list에 중간에서 부터 탐색이 시작됩니다. 그렇게 하다보면 일일이 하나 씩 Searching하는 것 보다 더 효율적이겠죠.

Python 코드로 구현해보았습니다.

3 가지가 핵심인데요. 이 3가지로만 Loop를 돌리게 되면 금방 탐색을 할 수 있죵.

lower - 시작 변수 
upper - 끝 변수
middle = 시작과 끝의 중간 변수 

1 2 3 4 5 6 7 8 9 10 11

def solution(L, x): lower = 0 upper = len(L) - 1 answer = -1 while ( lower <= upper ): middle = (lower + upper)//2 if L[middle] > x: upper = middle-1 elif L[middle] < x: lower = middle+1 else: return middle return answer