[알고리즘 기초] 이진 검색 ( binary search algorithm)

#코드는 공부용으로 구현해본거라 틀릴수도있음

## 파이썬

 

이진검색이란 ?

자료 가운데 항목의 키값과 비교해서 다음 검색 위치를 결정해서 검색하는 방식 ( 무조건 정렬된 형태여야한다)

검색 범위를 반으로 줄여가며 빠르게 검색할 수 있다 (O(logN) 으로 순차보다 빠르다

 

과정 : 

1, 자료 중앙의 원소를 선택

2, 중앙값과 목표값을 비교

3, 목표값 < 중앙값 : 자료의 왼쪽 반에 대해서 새로 검색을 수행

    목표값 > 중앙값 : 자료의 오른쪽 반에 대해서 새로 검색을 수행

 

값을 찾을때까지 반복

 

#이진검색
def solution(L,x):
    lower = 0
    upper = len(L)-1
    while lower <= upper:
        middle = (lower+upper) //2 #중간값
        if L[middle] == x:
            return middle
        elif L[middle] < x :
            lower = middle +1
        elif L[middle] > x :
            upper = middle -1
    return -1

L = [1,2,3,4,5,6,7,8,9]
x=8
print(solution(L,x))