이진탐색

def binarySearch(list, value):
    front = 0 시작과 함께 값을 제일 작은 인덱스로 초기화
    rear = len(list) - 1 시작과 함께 제일 큰 값으로 인덱스를 초기화했다

    while front <= rear: 프로트로 설정한 값이 후미로 설정한 값보다 작을 때까지만 반복한다
        mid = (front + rear) // 2 
//미드 값을 설정하는 주의해야 하는 점은 파이썬은 정수나눗셈이 이란거다
        if list[mid] == value: 미드값과 찾으려는 값이 같다면 바로 반환한다.
            return mid
        if list[mid] > value: 미드값이 찾으려는 값보다 크면 후미값을 미드값 -1러 바꾸어 준다.
            rear = mid - 1
        else: 미드 값이 찾으려는 값보다 작은경우에는 프론트 값을 미드값보다 하나 크게 설정해 준다.
            front = mid + 1

이진탐색은 값의 탐색에 있어서 가장 빠르다는 장점을 가진다 그 이유는 시간복잡도에서 나오는데 이진탐색법으 시간복잡도는 log2 n을 가진다 이는 그 이유는 연산을 실행할 수록 탐색 대상이 반으로 줄어들기 때문이다.

def interPolaration(list, value):
    high = len(list) - 1
    low = 0
    while high >= low:
        mid = int(low + (high - low) * ((value - list[low]) / (list[high] - list[low])))
        if list[mid] == value:
            return mid
        if list[mid] < value:
            low = mid + 1
        else:
            high = mid - 1
    return None

mid = int(low + (high - low) * ((value - list[low]) / (list[high] - list[low])))

위의 이진탐색과 유일하게 다르점이 바로 미드를 설정하는 과정이다 이는 탐색값과 위치는 비례한다는 가정하에 유도된 공식이다.