2주차의 키워드 중 하나인 이진검색에 대한 이론을 정리해보고자 한다.

정의

: 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색

→배열의 데이터가 오름차순이나 내림차순으로 정렬 sort되어 있어야 함.

→선형탐색을 어떻게 효율적으로 할것이냐→베스킨라빈스31 게임전략처럼

31→16→16언더?→8업다운?→4업다운?→처럼 반으로 쪼개서 원하는 값을 효율적으로 찾아내는 방법

---

방법

: 내가 탐색할 리스트를 정의하고 범위를 정하자

맨앞(start) 중앙(mid): 요건이 충족되는지 판단값 끝(end)

while(start<=end): 조건에서 즉, 선형탐색을 진행하면서

mid > key: 윗값 범위 제외, end=mid-1로 업데이트

mid < key: 아랫값 범위 제외, start=mid +1로 업데이트

---

적용할 문제 유형

1. 선형탐색인데 탐색 범위가 매우 클 경우 적용

2. 파라메트릭 서치(최적화 문제를 결정 문제(예, 혹은 아니오)로 바꾸어서 해결하는 기법) 문제

---

기본예제

def bin_search(a, key):
    """시퀀스 a에서 key와 일치하는 원소를 이진 검색"""
    pl = 0           # 검색 범위 맨 앞 원소의 인덱스
    pr = len(a) - 1  # 검색 범위 맨 끝 원소의 인덱스

    while (pl <= pr):
        pc = (pl + pr) // 2  # 중앙 원소의 인덱스 #판단 기준!
        if a[pc] == key:
            return 1    # 검색 성공
        elif a[pc] < key:
            pl = pc + 1  # 검색 범위를 뒤쪽의 절반으로 좁힘
        else:
            pr = pc - 1  # 검색 범위를 앞쪽의 절반으로 좁힘
    return 0            # 검색 실패

for i in m_arr:
    print(bin_search(n_arr,i))


def count(arr, left, right):
    left_index = bisect.bisect_left(arr, left)
    right_index = bisect.bisect_right(arr, right)
    return right_index-left_index


for i in m_arr:
    if count(n_arr, i, i) != 0:
        print(1)
    else:
        print(0)