[Algorithm] 이진 탐색 (Binary Search)

*순차 탐색 (Sequential Search)

-데이터를 차례대로 확인하는 방법

-시간복잡도 : O(N)

# 반복문

def sequential_search(data, target):
    for i in range(len(data)):
        if target == data[i]:
            return i + 1


data = list(input().split())
target = input()

print(sequential_search(data, target))

 

*이진 탐색 (Binary Search)

-데이터가 정렬되어있는 경우에 사용

-시작점, 중간점, 끝점

-찾으려는 데이터와 중간점 위치의 데이터를 비교

-한 번 확인할 때마다 확인할 원소의 갯수가 절반으로 줌

-시간 복잡도 : O(logN)

# 반복문

def binary_search(data, target):
    start = 0
    end = len(data) - 1
    
    while start <= end:
        mid = (start + end) // 2
        
        if target == data[mid]:
            return mid + 1
        elif target < data[mid]:
            end = mid - 1
        else:
            start = mid + 1
    
    return None


data = list(map(int, input().split()))
target = int(input())

print(binary_search(data, target))

# 재귀 함수