[코딩테스트: Python] 이진(이분) 탐색 (Binary Search)

본 내용은 하단 참고 링크의 블로그로 공부하고 기록을 위해 작성하였습니다.

👨🏻‍💻 이진탐색/이분탐색 알고리즘?

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다.
• 배열 내부의 데이터가 정렬되어 있어야만 사용 가능하다.
• 변수 3개(start, end, mid)를 사용해서 탐색을 하고, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이다.

즉, 정렬된 배열에서 원하는 숫자(target)을 찾는 알고리즘으로 배열 전체의 중간값을 target 값과 비교하고 중간값이 target값보다 크면 왼쪽 부분만 선택한다. 그리고 왼쪽 부분의 중간값을 다시 target과 비교하는 방법이다.

🧐 How?

이진 탐색을 푸는 방법은 아래와 같이 2가지 방향을 잡을 수 있다.

• 정방향으로 푸는 방법
• 재귀를 사용해서 푸는 방법

👨🏻‍💻 Source Code

🧐 정방향

target = 3
m_list = [14, 2, 13, 6, 1, 7, 9, 10, 8, 11, 3, 4]
length = len(m_list)

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

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

🧐 재귀(Recursive)

def binarySearch(array, target, left, right):
	middle_index = (left + right)//2
    print(middle_index)
    middle = array[middle_index]
    if target == middle:
    	print('answer {}'.format(middle_index))
    elif middle > target:
    	binarySearch(array, target, left, middle_index - 1)
    elif middle < target:
    	binarySearch(array, target, middle_index + 1, right)
    else:
    	return False
 
target = 3
m_list = [14, 2, 13, 6, 1, 7, 9, 10, 8, 11, 3, 4]
length = len(m_list)

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

binarySearch(m_list, target, 0, right)

🔗 Reference

https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search
https://wayhome25.github.io/cs/2017/04/15/cs-16/