[알고리즘] 7주차 이진탐색

nerry·2022년 2월 22일

DPT 알고리즘

알고리즘

목록 보기

47/86

이진탐색

정렬된 배열에서 타겟을 찾는 검색 알고리즘
자료구조인 이진 탐색 트리와 알고리즘 그 자체이다.
탐색할 자룔르 둘로 나누어 해당 데이터가 있을 만한 곳을 탐색하는 방법

동작

정렬된 배열에서 가장 가운데 값과 키 값을 비교한다.
가운데 위치한 값이 키 값과 같으면 이 값의 위치를 반환한다.
키 값이 더 크다면 가운데 값을 기준으로 오른쪽을, 키 값이 더 작다면 왼쪽을 탐색한다.
키 값을 찾을 때 까지 반복한다.

구조

분할 정복 알고리즘을 이용함

Divide ande Conquer
- Divide : 문제를 하나 또는 둘 이상으로 나눈다.
- Conquer : 나눠진 문제가 충분히 작고 해결이 가능하다면 해결하고 그렇지 않으면 다시 나누기

➡️ 이진 탐색

Divide : 리스트를 두 개의 서브 리스트로 나눔
Conquer
- 검색할 숫자 > 중간 값 : 뒷 부분의 서브 리스트에서 숫자 찾기
- 검색할 숫자 < 중간 값 : 앞 부분의 서브 리스트에서 숫자 찾기

구현

재귀

def binary_search(left,right):
	if left<= right:
    	mid = (left+right)//2
        
        if nums[mid]<target:
        	return binary_search(mid+1,right)
       	elif nums[mid]>target:
        	return binary_search(left,mid-1)
        else:
        	return mid
    else:
    	return -1

반복

def binary_search():
	left,right=0,len(nums)-1
    while left<=right:
    	mid=(left+right)//2
        
        if nums[mid]<target:
        	left=mid+1
        elif nums[mid]>target:
        	right=mid-1
        else:
        	return mid
    return -1

모듈 bisect 사용하기

def binary_search():
	index=bisect.bisect_left(nums,target)
    
    if index<len(nums) and nums[index]==target:
    	return index
    else:
    	return -1

bisect_left(a, x) --> 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메소드
bisect_right(a, x) --> 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메소드

➡️ bisect라이브러리(모듈)은 '정렬된 리스트'에서 '값이 특정 범위에 속하는 원소의 개수'를 구할 때 사용하면 효율적이다.

# 효율적 예시
from bisect import bisect_left, bisect_right

# '정렬된 리스트'에서 `값이 특정 범위에 속하는 원소의 개수`를 구할 때 좋다.
def count_by_range(b, left_value, right_value):
    right_index = bisect_right(b, right_value)
    left_index = bisect_left(b, left_value)
    print('right : ', right_index, 'left :', left_index)
    return right_index - left_index


a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
print(count_by_range(a, 4, 4))
>>> right :  8 left : 6
>>> 2
# 리스트 a에 4는 총 2개 존재한다.

print(count_by_range(a, -1, 3))
>>> right :  6 left : 0
>>> 6
# 리스트 a에 -1~3사이의 값은 총 6개 존재한다.