[알고리즘] 이분탐색 (Binaray Search)

알고리즘을 풀다 보면 시간복잡도의 늪에 빠질 때가 있다.

 

 

특히 수의 범위가 크면  배열 내 특정한 값을 찾을 때 

아래와 같은 방식은 모든 배열을 탐색하기 때문에 엄청난 시간이 걸리게 된다.,

 

i in arr

 

 

 

 

 

 

 

 

 

이럴때 사용할 수 있는 이분탐색!

이분탐색은 배열에서 특정한 값을 찾을 때 순차 탐색처럼  매번 모든 데이터를 체크하여 값을 찾는게 아니라,

탐색범위를 절반씩 줄여가며 찾아가는 search 방법이다.

 

그림을 엉성하게 그렸지만 이분탐색을 아주 직관적이게 표현해보았다. 😎

 

 

그렇다면 코드 구현 시에 어떻게 표현될까?

 

---

 

 

지극히 개인적이지만  알고리즘 문제를 만났을 때 적용할만한 유형을 크게 3가지로 분리했는데,

1) 배열내 특정한 값의 idx를 찾을 때  2) 배열내에서 특정한 값이 추가될 때의 그 idx  3) 

 

 

 

 

1) 배열내 특정한 값의 idx를 찾을 때

arr = [1,2,4,5,7] 

def bin_search(target,data):
    start = 0
    end = len(data)-1
    findSuc = 0
    while start <= end:
        mid = (start+end)//2
        if data[mid] == target:
            return mid
            break
        elif data[mid] <= target:
            start = mid +1
        else:
            end = mid-1
    return -1
    
    

print(bin_search(4,arr)); // 2

 

 

2) 배열 내 특정한 값이 추가될 때 그 idx (오름차순)

==

배열 내 특정한 값의 오른쪽 인덱스 구하기 bisect_right

배열내 특정한 값이 추가될 때 그 자리가 정렬된 순서에서 어떤 idx인지 알려주는 것인데,

target이 배열 내에 없어도 그 위치를 찾아낼 수 있다.

 

arr= [1,2,4,5,7]

def bin_search(target,data) :
    start=0
    end=len(data)-1

    while(start<=end):
        mid=(start+end)//2

        if data[mid] <=target:
            start=mid+1
        else:
            end=mid-1
            
    return start

print(bin_search(4,arr)); // 3
print(bin_search(3,arr)); // 2

 

라이브러리 사용 시

해당 로직은 라이브러리로도 쉽게 사용할 수 있는데 bisect_right 

bisect_left(literable, value) : 왼쪽 인덱스를 구하기

from bisect  import bisect_right 

arr= [1,2,4,5,7]

print(bisect_right(arr,4)) // 3
print(bisect_right(arr,3)) // 2

 

 

3) 배열 내 특정한 값의 왼쪽 인덱스 구하기 bisect_left

 

from bisect  import bisect_right 

arr= [1,2,4,5,7]

print(bisect_right(arr,4)) // 2
print(bisect_right(arr,3)) // 1

 

 

 

---

 

특히 bisect_left 와 bisect_right는 정말 헷갈려서 어떻게 익숙하게 만들 수 있을까 고민을 했는데,

 

 

예시로 

arr=[1,2,4,5,7]

#right
bisect_right(arr,4) # 있을 때
bisect_right(arr,3) # 없을 때

#left
bisect_left(arr,4) # 있을 때
bisect_left(arr,3) # 없을 때

 

 

이렇게 해당하는 target 값을 배열에 넣은 후에 그 인덱스를 비교해서 어떤 값이 나올지 비교해보며 정리했더니

확실하게 정리가 되었다. 절대 잊어버리지 않을 것 같다.

 

 

 

 

 

참고: https://programming119.tistory.com/196 [개발자 아저씨들 힘을모아]