순차탐색(sequential search), 이진탐색(binary search)

순차탐색

: 말 그대로 순차적으로 모든 데이터들을 확인하면서 탐색하는 방법

: list내에 특정 원소를 찾는 경우, 원소의 개수를 세는 경우

: 시간복잡도 O(n), 최악의 경우 모든 원소를 다 확인해야 하기에

 

이진탐색

: binary search

: "정렬된 데이터"임을 전제로 사용할 수 있는 방법

: 탐색범위를 절반으로 좁혀가면서 탐색할 수 있는 방법

: O(logn)의 시간복잡도

-- 데이터 개수가 2배 늘어날 때, 탐색 횟수가 한 번 증가한다

-- W(2^k) = k+1 , W(k) = logn +1 

 

python을 바탕으로 한 이진탐색의 구현

- 재귀, 반복 두 가지 방법 존재

import sys
#반복문을 통한 구현
def binary_search_1(data, n, target):
	low, high = 0, len(data)-1 # high = n-1
    while low <= high:
    	mid = low+high//2
        if data[mid] == target: # found!
        	return mid
        elif data[mid] > target:
        	high = mid-1
        else:
        	low = mid+1
    return None
    
n= int(input())
target = int(input())
data = list(map(int, input().split()))
#data = list(map(int, sys.stdin.readline().split()))

location_out = binary_search(data, n, target)

print(location_out)

data[mid] < target

•  low--mid--target--high 순서로 구성되어 있는 것을 뜻함으로 low값을 mid+1로 수정해 low--target--high로 만들고 반복 
• 오른쪽 절반을 선택해 반복

data[mid] > target

•  low--target--mid--high 순서로 구성되어 있는 것을 뜻함으로 high값을 mid-1로 수정해 low--target--high로 만들고 반복
• 왼쪽 절반을 선택해 반복