이진 검색

Binary Search

: 자료의 가운데 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

-> 키를 찾을 때까지 검색 범위를 반으로 줄여나가면서 순환하므로 보다 빠르게 검색 가능

 

 

 단, 이진 검색을 하기 위해서는 자료가 정렬되어 있어야 함

 

 

검색 과정

1. 자료의 중앙에 있는 원소를 고른다.

2. 중앙 원소의 값과 키 값이 같은 지 비교한다.

3. 키 값이 중앙 원소보다 작으면 자료의 왼쪽 반에 대해서 새롭게 검색을 수행하고, 크다면 오른쪽 반에서 수행한다.

4. 1~3의 과정을 값을 찾을 때까지 반복한다.

 

 

 

구현

 

1. 반복 구조로

# 반복구조
def binarySearch(S, key):
    low = 0
    high = len(S)-1

    while low <= high:
        mid = int(low + (high - low) / 2)

        if S[mid] == key:
            return mid
        elif S[mid] > key:
            high = mid - 1
        else:
            low = mid + 1
    
    return -1

 

 

2. zㅐ귀

# 재귀
def binarySearch(A, low, high, key):
    if low > high:
        print(-1)
        return 

    mid = (low + high) // 2
    if key == A[mid]:
        print(mid)
        return

    if key > A[mid]:
        binarySearch(A, mid+1, high, key)
    else:
        binarySearch(A, low, mid-1, key)

 

 

 

 

연습문제 - SWEA_5207_이진탐색

 

문제 설명을 진짜 못해놨네,,,ㅎ

- '번갈아'  오른쪽 왼쪽 탐색하는게 포인트

 

코드

import sys
sys.stdin = open('5207_input.txt', 'r')

T = int(input())


# 반복구조
def binarySearch(S, key):
    low = 0
    high = N - 1
    visited = ['*']

    while low <= high:
        mid = (low + high) // 2

        if S[mid] == key:
            return visited

        elif S[mid] > key:
            visited.append('l')
            high = mid - 1
        else:
            visited.append('r')
            low = mid + 1

    return -1


for test_case in range(1,T+1):
    N, M = map(int, input().split())

    A = sorted(list(map(int, input().split())))

    B = list(map(int, input().split()))

    cnt = 0
    for b in B:
        res = binarySearch(A, b)
        if res != -1 and 'rr' not in ''.join(res) and 'll' not in ''.join(res):
            cnt += 1


    print(f'#{test_case} {cnt}')