이진탐색(Binary search)

탐색

• 선형탐색
  : '순차적'으로 모든 요소들을 탐색.
• 이진탐색
  : 최소, 최대, 중간 인덱스를 찾아 값이 최소-중간, 중간-최대 인경우로 나누어 탐색.

문제) 리스트 L과 그 안에 있는 값 x를 찾으려 할 때, x값의 인덱스를 구하시오(단, x값이 존재하지 않으면 -1을 리턴)
예1)
L = [2, 3, 5, 6, 9, 11, 15]
x = 6
의 인자들이 주어지면, L[3] == 6 이므로 3 을 리턴.

예2)
L = [2, 5, 7, 9, 11]
x = 4
로 주어지면, 리스트 L 내에 4 의 원소가 존재하지 않으므로 -1 을 리턴.

풀이)
배열의 최대, 최소, 중간 값을 계산하여 x값의 인덱스를 찾을 때까지 반복한다.

비효율적(선형)

def solution(L, x):
    answer = -1
    
	# 배열을 순차적으로 순회하며 원하는 값(x)이 나올 때 까지 계속 탐색한다.
	# 하지만, 원하는 값이 배열의 가장 끝에 있으면 낭패;;;
	for index, element in enumerate(L) :
		if element == x:
			answer = index
    
    return answer

효율적(이진)

def solution(L, x):
    answer = -1
    lower = 0
    upper = len(L) - 1
    
    # 최대, 최소 값을 셋팅하고, 중간 값을 계산하여 x값의 인덱스를 구한다.
    while lower <= upper :
    	# x값이 최대, 혹은 최소값 부근에 존재하는 경우를 대비
        middle = lower + (upper - lower) // 2

        if L[middle] == x:		# x값을 찾을 경우.
            answer = middle
            break
        elif L[middle] < x:		# x값이 배열의 오른쪽에 있다면, 최소값을 조정
            lower = middle + 1
        else:				# x값이 배열의 왼쪽에 있다면, 최대값을 조정
            upper = middle - 1

    return answer

효율적(이진) - 재귀(함수의 호출을 위해, 최소(l), 최대(u)인자를 추가

def solution(L, x, l, u):
    if l > u:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l, mid - 1)
    else:
    	return solution(L, x, mid + 1, u)

출처: 프로그래머스 강의 "어서와! 자료구조와 알고리즘은 처음이지?"