[알고리즘] binary search(이진 탐색/이분 탐색)

정렬된 list에서 query item을 찾아서 위치를 return한다.

 

1. list를 오름차순으로 정렬한다.

2. left = 0, right = n-1부터 시작한다.

3. middle = (start + end) / 2라고 두고 list[middle]과 query를 비교한다.

    1) query < list[middle]이면

        right을 middle-1로 둔다.

    2) query = list[middle]이면

        return middle

    3) query > list[middle]이면

        left를 middle+1로 둔다.

 

이때 query가 list에 없으면 무한루프를 돌 수가 있다.

따라서 left<=right일 때만 반복하도록 한다.

(left > right면 없다고 return한다.)

이진 탐색 소스코드: 재귀적 구현 (Python)

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_serarch(array, target, start, mid-1)
    
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
    	return binary_search(array, target, mid+1, end)
    
# n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기
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)

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

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(찾고자 하는 값)을 입력 받기
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)

출처: 이것이 코딩테스트다, https://www.youtube.com/watch?v=-Gx0T92-7h8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=28