이진탐색
-
[Python] bisect 함수를 통해 이진탐색 구현하기프로그래밍/알고리즘 2022. 9. 21. 22:08
이번 글에서는 파이썬 언어에서 bisect 함수를 통해서 이진탐색을 구현한다. 1. Bisect 함수 리스트 lst와 숫자 x가 있을 경우(lst는 정렬되어 있다고 가정한다), x가 lst의 어느 위치에 들어가야 정렬된 리스트가 유지되는지 반환한다. from bisect import bisect lst = [1,3,5,7,9] x = 7 # lst에 '7'이라는 값이 어디에 들어가야 정렬된 리스트를 유지하는지 bisect(lst,x) # 4라는 인덱스값을 반환함 2. Bisect의 네가지 케이스 2.1 동일한 값이 있을 경우 lst에 동일한 값이 있기 때문에 '7'의 다음 인덱스인 4를 반환한다. lst = [2,3,5,7,9] x = 7 bisect(lst,x) #=> 4 2.2 동일한 값이 없을 경우..
-
[Python]이진탐색 재귀함수로 구현해보기(recursion binary search)프로그래밍/알고리즘 2022. 9. 20. 20:24
이번 글에서는 파이썬 언어를 사용하여 재귀함수 기반 이진탐색을 구현합니다. 1. 이진탐색으로 같은 값 찾기 문제 리스트와 목표값이 주어졌을 때 값이 존재한다면 인덱스를 반환하고 없다면 -1을 반환해라. 이때 리스트는 정렬되어 있다. def binary_search(lst,start_p,end_p,target): mid_p = (start_p+end_p)//2 # 중앙 포인트 생성 #전체 탐색후 값이 없다면 -1 반환 if start_p>=end_p: return -1 # 중앙값이 목표값이라면 해당 인덱스 반환 if lst[mid_p] == target: return mid_p # 목표값보다 중앙값이 크다면 시작값부터 중앙값 이전까지 다시 탐색 elif target < lst[mid_p]: return b..