[알고리즘] 이진탐색 알고리즘

유튜브 이코테 강의를 듣고 정리한내용이다.

 

이진탐색 vs 순차탐색

* 이진탐색 : 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법(시작점, 끝점, 중간점을 이용해 탐색 범위를 설정한다.)
* 순차탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

 

=> 이진 탐색의 시간 복잡도는 단계마다 탐색 범위를 2로 나누는 것과 동일 하므러 연산횟수는 log2N에 비례한다. 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간복잡도는 O(logN)을 보장한다.

 

 

이진 탐색 재귀적 구현

#이진 탐색 소스코드 재귀함수로 구현
def binary_search(array, target, start, end):
    if start > end :
        return None
    mid = (start + end) // 2
    
    #바로찾은 경우 중간점 인덱스 반환
    if array[min] == target:
        return mid
    #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[min] > target:
        return binary_search(array, target, start, min-1)
    #중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else :
        return binary_search(array, target, mid+1, end)
        
#n(원소개수)과 target(찾을 값)을 입력받기
n, target = list(map(int, input().split()))
#전체 원소 입력 받기
array = list(map(int, input().split()))

#이진탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)
if result == None : 
    print("원소가 존재하지 않습니다.)"
else :
    print(result + 1)

 

 

이진 탐색 반복문 구현

#이진 탐색 소스코드 반복문으로 구현
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        #바로 찾은 경우 중간점 인덱스 반환
        if array[mid] == target :
            return mid
        #중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target : 
            end = mid - 1
        #중간점의 값보다 찾고자 하는 갑이 큰 경우 오른쪽 확인
        else : 
            start = mid + 1
    return None
        
#n(원소개수)과 target(찾을 값)을 입력받기
n, target = list(map(int, input().split()))
#전체 원소 입력 받기
array = list(map(int, input().split()))

#이진탐색 수행 결과 출력
result = binary_search(array, target, 0, n-1)
if result == None : 
    print("원소가 존재하지 않습니다.)"
else :
    print(result + 1)

 

 

문제 : 정렬된 배열에서 특정 수의 개수 구하기

Q. N개의 원소를 포함하고 있는 오름차순 수열이 있을 때, 수열에서 x 가 등장하는 횟수를 계산하시오.

 예를 들어 {1,1,2,2,2,2,3} 수열에서 x가 2라면 2원소가 현재 4개이므로 4를 출력해야한다. 이 문제는 시간복잡도 O(logN)으로 설계하지 않으면, 시간초과처리.

A. 특정값이 등장 하는(x) 첫번째 위치와 마지막 위치를 찾아 그 차이를 계산해 해결.

파이썬의 bisect 라이브러리를 사용

 

bisect_left(literable, value) : literable 의 value 중 가장 왼쪽 인덱스를 리턴

bisect_right(literable, value) : literable 의 value 중 가징오른쪽 인덱스를 리턴

 

from bisect import bisect_left, bisect_right

def count_by_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index
    
n,x = map(int, input().split()) #데이터 개수 n, 찾을 값 x 입력받기
array = list(map(int, input().split())) #전체 데이터 입력받기

#값이 [x,x] 범위에 있는 데이터의 개수 계산
count = count_by_range(array, x, x)

#값이 x인 원소가 존재하지 않는다면
if count == 0 :
    print(-1)
#값이 x인 원소가 존재한다면
else : 
    print(count)