이진 탐색은 이미 자료구조를 공부하면서트리와 이진트리로 공부했던 내용이다. 전체적으로 다시 훑어보자는 마음으로 간단하게 정리하였다.

순차탐색

순차탐색 소스코드

def sequential_search(n,target,array):
        for i in range(n):
            if array[i]== target:
                return i + 1
                #인덱스는 0부터 시작하므로!
print("생성 원소 개수 입력 후 스페이스 입력 후 검색할 문자열 입력하세요")

input_data = input().split()
n = int(input_data[0])
target = int(input_data[1])

print("원소 개수만큼 문자열 입력하세요")
array = input().split()

print(sequential_search(n,target,array))

순차 탐색의 시간복잡도

: O(N) -> 순차적으로 하나씩 데이터를 확인하므로

이진 탐색

: 이진 탐색은 정렬된 상태에서 사용 가능

• 이진탐색은 변수 3개를 사용(찾으려는 데이터의 시작점, 끝점, 중간점)

• 이진 탐색은 코딩 테스트에서 단골로 나오는 문제이므로 꼭 외우자!

• 특히 이진 탐색은 어려운 문제에서 다른 알고리즘과 함께 사용한다.

• 이진 탐색 문제는 입력 데이터가 많거나 탐색 범위가 넓기 때문에, 데이터 개수가 1000만개를 넘거나, 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘일 확률이 높다

• 입력 데이터가 많을 때는 input()함수 말고 sys 라이브러리의 readline()함수를 이용하면 시간 초과를 피할 수 있다.

sys 라이브러리의 readline()함수

• sys 라이브러리를 사용할 때 한 줄 입력 후 rstrip()함수를 반드시 호출!
• readline()으로 입력하면 엔터가 줄 바꿈 기호가 된다.

readline()함수를 이용하여 입력값 받는 소스코드

import sts

input_data = sys.stdin.readline().rstrip()

print(input_data)

재귀 함수로 구현한 이진 탐색 소스코드

def binary_search(array, target, start,end):
    if start > end:
        return None
    mid = (start + end) // 2
    
    if array[mid] == target:
        return mid
    elif array[mid] > target :
        return binary_search(array, target, start, mid-1)
        ##중간값이 타겟보다 크면 중간값 기준 오른쪽은 모두 타켓보다 크므로 왼쪽 탐색(end를 mid-1로 대체)
    else :
        return binary_search(array,target,mid+1, end)
        ##중간값이 타겟보다 작으면 중간값 기준 왼쪽은 모두 타켓보다 작으므로 오른쪽 탐색(start를 mid+1로 대체)
    
    n, target = list(map(input().split()))
    
    result = binary_search(array, target, 0, n-1)
    if result == None:
        print("원소 존재하지 않음")
    else:
        print(result + 1)

이진 탐색의 시간 복잡도

: O(logN) -> 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어듦