이진 탐색, 순차 탐색

👀 이진 탐색이란?

: 데이터가 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘입니다.

배열의 중앙에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교합니다.

X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로

X가 중간 값보다 크면 중간 값을 기준으로 우측의 데이터들을 대상으로 다시 탐색합니다.

동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교하여 해당 값을 찾을 때까지 이 과정을 반복합니다.

 

👀 순차 탐색이란?

: 데이터가 담겨이는 배열을 앞에서 부터 하나씩 비교해서 원하는 데이터를 찾는 방법

 

👉 이진 탐색과 순차 탐색 과정 비교

 

👉 업다운 게임을 예로 들어 이진 탐색과 순차 탐색을 비교 해보겠습니다.

 

👉 순차 탐색을 사용한 예제 풀이

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_sequential(target, array):
    for number in array:
        if target == number:
            return True

    return False


result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result)  # True

array를 따라가면서 target이 존재한다면 true를 반환하고 끝까지 없다면 false를 반환하는 코드입니다.

 

👉 이진탐색을 사용한 예제 풀이

이진 탐색을 사용 할 경우 위와 같이 표현 할 수 있다.

 

이를 코드로 구현 해보면

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array) - 1
    current_guess = (current_min + current_max) // 2

    while current_min <= current_max:
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_min + current_max) // 2

    return False


result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

while문을 사용해서 current_min이 current_maz 이하일 때만 반복하고

if문을 사용해서 target의 위치를 찾고 target이 비교 대상보다 크다면 뒤를 비교하고

target이 비교 대상보다 작다면 앞을 비교한다.

---

이진탐색 출처

https://cjh5414.github.io/binary-search/

이진 탐색(Binary Search) 알고리즘 개념 이해 및 추가 예제

 

순차탐색 출처

https://syujisu.tistory.com/159

순차 탐색 (Sequential Search)