[알고리즘] 이진 탐색 (Binary Search)

jeyong·2023년 1월 31일

알고리즘 이진탐색

알고리즘 공부 정리

목록 보기

9/16

1.이진 탐색

오름차순으로 정렬된 배열에서 원하는 숫자(target)을 찾는 알고리즘

배열 전체의 중간값을 target 값과 비교

중간값이 target 값보다 크면 왼쪽 부분만 선택

왼쪽부분의 중간값을 다시 target 과 비교

2.이진 탐색의 장단점

장점

검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠름

단점

검색 원리상 정렬된 리스트에만 사용할 수 있음

특징

3.이진 탐색 구현

- 반복문 사용

target = 25
m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
length = len(m_list)

m_list.sort()![](https://velog.velcdn.com/images/joon6093/post/b51d5474-f876-4336-9685-e93f70e439b7/image.png)

left = 0 
right = length-1

while left<=right:
    mid = (left+right)//2
    if m_list[mid] == target:
        print(mid+1)
        break
    elif m_list[mid]>target:
        right = mid-1
    else :
        left = mid+1

- 재귀 사용

def binarySearch(array, target, left, right):
    middle_idx = (left+right)//2
    print(middle_idx)
    middle = array[middle_idx]
    if target == middle:
        print('answer {}'.format(middle_idx))
    elif middle > target:
        binarySearch(array, target,left,middle_idx-1)
    elif middle < target:
        binarySearch(array, target,middle_idx+1,right)
    else: 
        return False

target = 25
m_list = [30, 94, 27, 92, 21, 37, 25, 47, 25, 53, 98, 19, 32, 32, 7]
length = len(m_list)

m_list.sort()
left = 0 
right = length-1

binarySearch(m_list,target,0,right)

시간 복잡도

이진 탐색 알고리즘의 이진탐색의 시간복잡도는 logN으로 표현할 수 있음

참고

4. 이진 탐색 라이브러리

bisect.bisect_left(정렬된 리스트, target)
정렬된 리스트에서 target을 insert할때의 위치

bisect.bisect_right(정렬된 리스트, target)
정렬된 리스트에서 target을 insert할때의 위치+1
※ bisect.bisect는 bisect.bisect_right와 동일함
bisect.insert()
bisect함수와 동일하게 작동하고 해당 인덱스에 값을 삽입을 해준다.

import bisect
a = [1,2,3,4,5]
x = 3
b = bisect.bisect_left(a,x)
2와 3 사이 인덱스인 2반환

c = bisect.bisect_right(a,x)
3과 4 사이 인덱스인 3반환

정렬된 리스트에서 특정 값이 몇번 등장하는지 확인
bisect.bisect_right(a, right) - bisect.bisect_left(a, left)