자료구조/알고리즘 - 이진탐색 (1)

이진탐색?

배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법

1억 개 목록을 선형탐색할 때, 1억 번을 연산해야 한다. 이진탐색으로 찾는다면, 27번 안에 찾을 수 있다.

import math

math.log2(100000000) # 26.575424759098897

파이썬 while로 이진탐색 구현

def binary_search(arr, target, start, end):
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid-1
        else:
            start = mid+1

print(binary_search([1,2,3,4,5,6,7,8,9],8,0,8)) # 7

파이썬 이진탐색 내장 함수 bisect

import bisect

arr1 = [i for i in range(1,100,2)] # [1, 3, 5, 7, 9, 11,.....99]

# 77이 몇 번째 있는지 확인
b = bisect.bisect_left(arr1, 77) # 38
print(b)


# 76이 몇 번째 있는지 확인
# 76은 배열 안에 없어서 커졌을 때의 인덱스를 반환
b = bisect.bisect_left(arr1, 76) # 38
print(b)


# 0이 몇 번 째 있는지 확인
# 0도 마찬가지로 배열안에 없어서 커졌을 때의 인덱스 반환
b = bisect.bisect_left(arr1, 0) # 0
print(b)


# 101은 마지막 인덱스까지 찾았지만 없어서
# 마지막 인덱스 + 1을 해서 반환, 결국 배열의 길이
b = bisect.bisect_left(arr1, 101) # 50
print(b)

bisect -> left, right 응용

# 30~60 사이의 값들
l = bisect.bisect_left(arr1, 30)
r = bisect.bisect_right(arr1, 60)
print(arr1[l:r])

#[31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59]

index vs bisect ( 정렬된 배열에서 )

import bisect

# 정렬된 배열에서 7의 위치를 찾고 싶을 때, index와 bisect 속도 비교
arr1 = []
for i in range(10000000):
    arr1.append(i)


start = time.time()
print('index')
arr1.index(8888888)
end = time.time()
print(f"{end - start:.5f} sec")
print('-------------')

print('bisect')
start = time.time()
bisect.bisect_left(arr1, 8888888)
end = time.time()
print(f"{end - start:.5f} sec")



#index
#0.22068 sec
#-------------
#bisect
#0.00004 sec

오늘 푼 문제

https://geonoo.tistory.com/124

https://geonoo.tistory.com/125

https://geonoo.tistory.com/126

https://geonoo.tistory.com/127

회고

오늘은 이진탐색을 배웠고 bisect라는 내장 함수를 공부해 봤다.

요즘은 내장 함수를 이용해서 빠르게 풀고 나서 이진탐색의 원리나 구조를 보고 내 손으로 직접 연습하고 있다.

아침에는 너무 정신이 없었다. CS 스터디 발표가 있는 날이라서 새벽에 발표자료 만드느라 조금 늦게 잤더니, 30분이나 지각을 해버렸다..

다음에는 조금만 일찍자고 지각하는 일은 없게 해야겠다. 생활 패턴이 바뀌면 시간 맞추는것도 어려워서 잘 유지해 나가야겠다.

 

하루가 금방 지나간 것 같다. 내일은 일요일이기에 일찍 마치고 쉬어야겠다 ^.^