정렬 알고리즘: 이진 탐색

순차 탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

이진 탐색: 정렬되어있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법.

(시작점, 끝점, 중간점 이용함)

 

n, target = list(map(int,input().split())) #데이터개수와 찾을 값
array = list(map(int,input().split()))

def binary_search(array, target, start, end):
    if start> end: 
        return None
    
    mid = (start + end) // 2 #중간점 인덱스
    if array[mid] == target: #타깃을 찾은 경우
        return mid
    elif array[mid] > target: #중간점의 값이 타깃보다 큰 경우
        return binary_search(array,target,start,mid-1)
    elif array[mid] < target: #중간점의 값이 타깃보다 작은 경우
        return binary_search(array,target,mid+1,end)


result = binary_search(array,target,0,n-1)
if result == None:
    print("원소가 존재하지 않음")
else:
    print(result+1)

정렬되어 있는 배열을 보고..

중간점의 값과 target값을 비교해서,

target이 중간값보다 작으면 => 중간값 뒷쪽에는 target이 있을리가 없음 => 중간값 앞쪽에서 다시 탐색

target이 중간값보다 크면 => 중간값 앞쪽에는 target이 있을리가 없음 => 중간값 뒷쪽에서 다시 탐색

 

대충 이런거라 보면 될듯..

 

반복문을 이용해서 구현할 수도 있는데 난 재귀함수 쓰는게 더 알아보기 쉬운거같다

 

반복문 쓰는경우엔 while start <= end: 안에다가 구현하면 됨..

 

---

파이썬 이진 탐색 라이브러리

bisect_left(a,x): #정렬된 순서를 유지하면서 배열a에 x를 삽입할 가장 왼쪽 인덱스를 반환
bisect_right(a,x): #정렬된 순서를 유지하면서 배열a에 x를 삽입할 가장 오른쪽 인덱스를 반환

이진탐색 라이브러리가 있다..

 

가장왼쪽 인덱스, 가장 오른쪽 인덱스.. 이건 같은값이 배열에 있을때 해당된다고 생각하면 될듯

 

이걸 이용해서.. 배열에 속한 값의 개수를 셀수도있고..그럼

 

 

---

파라메트릭 서치

최적화 문제를 예/아니오 로 바꾸어 해결하는 기법..

ex) 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제

 

여기에서 이진탐색을 사용하여 해결할 수 있음..

 

그 예시는 다음에 계속...