[크래프톤 정글] 12일 - 탐색

wnajsldkf·2023년 4월 14일

TIL algorithm jungle 이분 탐색 탐색

정글

목록 보기

6/14

오늘 한 일📝

이분 탐색 이론 공부

Algorithm 문제 풀이(1920, 2805, 8983, 2630)

이분탐색

탐색은 데이터 집합에서 원하는 값을 가진 원소를 찾아내는 알고리즘을 말한다. 대표적인 탐색 방법은 다음과 같다.

배열 검색
연결 리스트 검색
이진 검색 트리

선형 검색(Linear search)

직선 모양(선형)으로 늘어선 배열에서 검색하여 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 순서대로 검색하는 알고리즘을 말한다.

n의 복잡도를 갖는다.

검색 종료 조건

검색 실패: 검색할 값을 찾지 못하고 배열의 맨 끝을 지나는 경우(if i == len(a))
검색 성공: 검색할 값과 같은 원소를 찾는 경우(if a[i] == key)
배열 원소의 개수가 n일 때, 조건을 판단하는 횟수는 평균 n/2를 갖는다.

def seq_search(a, key):
	for i in range(len(a)):
		if a[i] == key:
			return i
	return -1

이진 검색(Binary search)

이진 검색 알고리즘을 사용하려면 데이터가 '정렬'되어 있는 상태여야 한다. 정렬된 상태에서 검색 범위를 줄여가면서 탐색하는 방식이다.

log n의 복잡도를 갖는다.

반복문 사용

def binary_search(a, key):
	pl = 0                   # 검색 범위 맨 앞 원소의 인덱스
	pr = len(a) - 1          # 검색 범위 맨 끝 원소의 인덱스

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

재귀 사용

def binary_serach(array, target, start, end):
	if start > end:
    	return -1				# 검색 실패
    mid = (start + end) // 2
    
    if array[mid] == target:	
    	return mid				# 검색 성공
    elif array[mid] > target:
    	return binary_search(array, target, start, mid-1)	# 검색 범위를 앞쪽 절반으로 좁힘
	else:
    	return binary_search(array, target, mid+1, end)		# 검색 범위를 뒤쪽 절반으로 좁힘

이진 탐색 심화
만약 찾는 값이 없다면, 인접한 원소를 전달해주는 코드를 작성해보자.

a = [1, 4, 5, 9, 10, 11, 11, 3]
a.sort()

def binary_search(numbers, key):
    left = 0
    right = len(numbers)-1

    while left <= right:
        middle = (left + right) // 2

        if key == numbers[middle]:
            print(middle)
            return middle
            break
        elif key < numbers[middle]:
            right = middle -1
        elif key > numbers[middle]:
            left = middle + 1

    # Not key in the list
    if right == -1:
        print(numbers[0])
    elif left == len(a):
        print(numbers[len(a)-1])
    else:
        prev_num = numbers[left-1]
        next_num = numbers[right+1]

        prev_step = abs(key - prev_num)
        next_step = abs(key - next_num)

        if prev_step == next_step:
            print(prev_num, next_num)
        elif prev_step > next_step:
            print(next_num)
        elif prev_step < next_step:
            print(prev_num)

binary_search(a, 8)