<binary search> 이진탐색

이진탐색

📌 이진탐색

1 ~ 50까지 오름차순 정렬된 카드 더미에서 28번 카드를 찾는 문제를 예시로 이분 탐색을 알아보겠습니다. 편의상 첫 번째 카드부터 i번째 카드는 v[i], 28은 val로 표기하겠습니다.

이 경우 결정 문제를 "v[i] >= val인가?"로 잡으면 결정 문제의 답은 i가 증가함에 따라 F, F, ..., F, T, T, ..., T와 같이 분포함을 알 수 있습니다. 이때 우리가 찾고자 하는 값은 처음으로 v[i] >= val인 지점, 즉 조건문이 처음 True가 되는 i값입니다.

• 정렬 등과 함께 가장 기초인 알고리즘으로 꼽히는 문제. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다.
• BigO : O(log N)
• 정렬된 자료를 반으로 나누어 탐색하는 방법
• 주의점 : 자료는 오름차순 으로 정렬된 자료여야 한다.
• 이진트리, 바이너리서치는 코딩 인터뷰 단골문제
• 퍼포먼스가 아주 좋고 구현하는 중에 dynamic programming, recursion을 볼 수 있다.

특징

• binary search (이진탐색) : 반드시 정렬된 상태에서 시작해야한다. 로그실행시간을 보장한다.
• 많은 최적화 문제는 이분 탐색으로 풀 수 있습니다. 최적화 문제란 어떤 조건(Check(x))을 만족하는 x의 최댓값 또는 최솟값을 찾는 문제를 말합니다.

---

📌 이진탐색 코드

// 의사코드
function 이진탐색(데이터, 찾는 값)

데이터가 혹시 비어 있는가?
(네) return 찾는 값 없음.

데이터의 가운데 지점을 찾는다.
찾은 지점의 값을 뽑는다.
뽑은 값이 찾는 값인가?

(네) return 뽑은 값.
(아니요)
  뽑은 값과 찾는 값을 비교한다.
  (뽑은 값이 찾는 값보다 큰 값인가?)
    return 이진탐색(데이터 앞쪽 절반, 찾는 값)
  (작은 값인가?)
    return 이진탐색(데이터 뒤쪽 절반, 찾는 값)

 

구현 코드

구현을 위한 준비

• target : 찾고자 하는 값
• data : 오름차순으로 정렬된 list
• start : data 의 처음 값 인덱스
• end : data 의 마지막 값 인덱스
• mid : start, end 의 중간 인덱스

# 재귀적 이진탐색
def binary_search(start, end):
    if start > end:
        return -1

    mid = (start + end) // 2

    if nums[mid] < target:
        return binary_search(mid + 1, end)
    elif nums[mid] > target:
        return binary_search(start, mid - 1)
    else:
        return mid

# 비재귀적 이진탐색의 Python 코드
def binary_search (arr, val):
    first, last = 0, arr.len()
    while first<=last:
        mid = (first + last) // 2
        if arr[mid] == val: return mid
        if arr[mid] > val: last = mid - 1
        else: first = mid+1
    return -1