이분 탐색(Binary Search)

 

오름차순으로 정렬된 배열에서 원하는 숫자(target)을 찾는 알고리즘입니다.

배열 전체의 중간값을 target 값과 비교

중간값이 target 값보다 크면 왼쪽 부분만 선택

왼쪽부분의 중간값을 다시 target 과 비교

정방향으로 푸는 방법과 재귀로 푸는 방법 두 가지가 있습니다.
정방향도 어떻게 보면 개념적으로는 재귀로 푸는 방법과 같은 방법입니다.

개념

• 정렬된 자료를 반으로 나누어 탐색하는 방법
• 주의점 : 자료는 오름차순 으로 정렬된 자료여야 한다.
• 이진트리, 바이너리서치는 코딩 인터뷰 단골문제
• 퍼포먼스가 아주 좋고 구현하는 중에 dynamic programming, recursion을 볼 수 있다.

특징

• linear search (순차검색) : 순서대로 찾는다. 성능평가시 비교대상으로 사용한다.
• linear search는 정렬 방식이 상관 없다.
• binary search (이진탐색) : 반드시 정렬된 상태에서 시작해야한다. 로그실행시간을 보장한다.
• 참고로 insert sort (삽입정렬), bubble sort, selection sort는 O(n^2)의 성능을 갖고 있다. (참고)

 

처음부터 끝까지 돌면서 탐색하는 것보다 훨씬 빠른 장점을 지님

* 시간복잡도
전체 탐색 : O(N)
이분 탐색 : O(logN)

진행 순서

• 우선 정렬을 해야 함
• left와 right로 mid 값 설정
• mid와 내가 구하고자 하는 값과 비교
• 구할 값이 mid보다 높으면 : left = mid+1 구할 값이 mid보다 낮으면 : right = mid - 1
• left > right가 될 때까지 계속 반복하기

source code

정방향

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

재귀(Recursive)

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)

 

출처

https://wayhome25.github.io/cs/2017/04/15/cs-16/ 

https://velog.io/@madfinger/Binary-Search%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%ED%8C%8C%EC%9D%B4%EC%8D%AC