Binary Search

정렬과 함께 가장 기초적인 알고리즘을 꼽힌다. 검색 범위를 줄여나가면 원하는 데이터를 검색하는 알고리즘

리스트와 같은 부분은 두개로 나누고 필요한 부분만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다.

리스트 중간 부분에서 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있느지 아래쪽에 있는지 판단하여 맨 앞부터 검색한다.

아래에 수도코드가 있다.

function 이진탐색(데이터, 찾는 값)

데이터가 혹시 비어 있는가?
(네) return 찾는 값 없음.

데이터의 가운데 지점을 찾는다.
찾은 지점의 값을 뽑는다.
뽑은 값이 찾는 값인가?

(네) return 뽑은 값.
(아니요)
  뽑은 값과 찾는 값을 비교한다.
  (뽑은 값이 찾는 값보다 큰 값인가?)
    return 이진탐색(데이터 앞쪽 절반, 찾는 값)
  (작은 값인가?)
    return 이진탐색(데이터 뒤쪽 절반, 찾는 값)

파이썬 코드로 아래와 같다.

def binary_search(arr: list, val):
    """
    비 재귀적 이진 탐색, 찾는 데이터가 arr에 있나??
    :param arr:
    :param val:
    :return:
    """
    first, last = 0, len(arr) - 1
    while first <= last:
        mid = (first + last) // 2
        if arr[mid] == val:
            return mid
        if arr[mid] > val:
            last = mide - 1
        else:
            first = mide + 1
    return -1

위 코드를 잘 분석해보자

val 값에 있는 것을 리스트에 있는지 찾아서 탐색하는 과정이다.

제곱근

제곱근에 대한 실수값을 조사하는 방법에서 이러한 알고리즘은 순방향과 역방향을 동시에 그리고 빠르게 근사값을 접근해감으로써 양쪽 방향으로 좁혀가는 강력한 수치해석방법으로 이진 탐색 알고리즘으로 정교하게 구현되어 질 수 있따.

참고자료