[알고리즘 기초] 이진 탐색 파이썬 코드

이진 탐색은 반으로 쪼개가면서 탐색을 하는 방식이다

*내부의 데이터가 정렬되어야만 사용이 가능하다는 특징이 있음

 

시작 , 끝 , 중간 데이터가 있어야 한다

찾으려는 데이터와 중간점의 데이터를 비교하고 다시 시작 , 끝 , 중간 을 조절해주면서 범위를 좁혀가는 탐색 방법이다

 

0 2 4 6 8 10 12 14 16 18   중에서 4 를 찾고자 한다면

 

0 2 4 6 8 10 12 14 16 18  

처음값 0 중간값 8 끝값 18  일때   찾으려는  4 보다 중간값인 8 이 더 크므로 더이상 8-16 까지의 데이터는 볼 필요가 없다 

그리고 끝 값을 8의 하나 앞인 인 6으로 해주자

 

0 2 4 6 8 10 12 14 16 18 

처음 값 0 중간값 2 끝값 6 일때 4는 중간값인 2보다 크므로 0-2 까지 의 데이터는 볼 필요가 없다 

그리고 시작 값을 2의 하나 앞인 4로 해주자

 

0 2 4 6 8 10 12 14 16 18 

처음값 4 중간값 4 끝값 6  중간점에 위치한 데이터 4 는 찾으려는것과 동일하므로 탐색을 종료한다

 

---

파이썬 코드 2가지 

1. 재귀

#이진 탐색 소스코드 구현 (재귀함수)

def binary_search(array,target,start,end):
    if start>end :
        return None
    mid = (start+end) // 2
    #찾은 경우 중간점 인덱스 반환
    if array[mid] == target :
        return mid
    #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target :
        return binary_search(array,target,start,mid-1)
    #큰 경우 오른쪽 확인
    else:
        return binary_search(array,target,mid+1,end)
    
n,target = list(map(int,input().split()))
#전체 원소 입력
array = list(map(int,input().split()))

result = binary_search(array,target,0,n-1)
if result == None:
    print("원소가 없습니다")
else:
    print(result+1)

 

2. 반복문

#이진 탐색 소스코드 구현 (반복문)

def binary_search(array,target,start,end):
    while start <= end :
        mid = (start+end) // 2 #중간점 찾기
        #찾은 경우 중간점 인덱스 반환
        if array[mid] == target :
            return mid
        #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid -1
        #중간점의 값보다 찾고자 하는 값이 큰 경우 왼쪽 확인
        else:
            start = mid +1
    return None
n, target = list(map(int,input().split()))
array = list(map(int,input().split()))

result = binary_search(array,target,0,n-1)
if result == None :
    print("원소가 존재하지 않습니다")
else:
    print(result + 1)