이진탐색

이진탐색이란?

• 데이터가 정렬돼 있는 배열(list)에서 특정 값 찾아내는 알고리즘
• 배열의 중간에 있는 임의의 값(mid)을 선택하여 찾고자 하는 target과 비교
• 처음의 start = 0, end = len(list) - 1
• list(mid) > target 이면 end - 1, list(mid) < target 이면 start + 1
• 위 과정을 반복하며 list(mid) == target 인 지점을 찾기
• 없을경우를 대비하여 while문의 종료시점은 start가 end를 넘어서는 시점

예시 코드

# 정방향
target = 25
m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
length = len(m_list)

m_list.sort()
left = 0
right = length-1

while left<=right:
    mid = (left+right)//2
    if m_list[mid] == target:
        print(mid+1)
        break
    elif m_list[mid]>target:
        right = mid-1
    else :
        left = mid+1

# 재귀
def binarySearch(array, target, left, right):
    middle_idx = (left+right)//2
    print(middle_idx)
    middle = array[middle_idx]
    if target == middle:
        print('answer {}'.format(middle_idx))
    elif middle > target:
        binarySearch(array, target,left,middle_idx-1)
    elif middle < target:
        binarySearch(array, target,middle_idx+1,right)
    else:
        return False

target = 25
m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
length = len(m_list)

m_list.sort()
left = 0
right = length-1

binarySearch(m_list,target,0,right)