이진탐색

''''
5. 이진탐색 알고리즘
순차탐색: 리스트 안에있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
이진탐색: 정렬되어 있는 리스트에서 탐색범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
- 이진탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정함 (O-notation: 로그~)
'''

from random import randint
# 동작 예시
num_list = [randint(0,20) for x in range(15)]
num_list.sort()
print("input ", num_list)

def binary_search(array, target,start,end):
    if start > end :
        return None

    mid = (start + end) // 2 # 몫은 "//" 연산
    if array[mid] == target:
        return mid

    if array[mid] > target:
        return binary_search(array, target, start, mid -1)
    else:
        return binary_search(array, target,mid+1,end)

n, target = len(num_list), 9
answer = binary_search(num_list, target,0,n)
if answer:
    print("answer : ", answer)
else:
    print("answer is None")

# 파이썬 이진 탐색 라이브러리
# biset_left - target의 idx를 구함
# biset_right- target의 idx+1(오른쪽) 를 구함
from bisect import bisect_left, bisect_right

def count_in_range(array, left_value, right_value):
    left_idx = bisect_left(array,left_value)
    right_idx = bisect_right(array, right_value)
    return left_idx,right_idx


# 값이 특정 범위에 속하는 데이터 개수 구하기
num_a, num_b = 4, 6
a, b = count_in_range(num_list, num_a, num_b)
print("more than {} ~{} ".format(num_a, num_b), a, b, num_list[a:b])
print("the number of dataset ", b-a)


'''
출제유형
파라메트릭 search - 최적화 문제를 결정(예/아니오) 문제
예) 특정한 조건을 만족하는 가장 알맞는 값을 빠르게 찾는 최적화 문제
'''