이진 탐색(1) 순차 탐색, 이진 탐색

순차 탐색 (Sequential Search)

• 이진 탐색을 알아보기 전에 가장 기본적인 탐색 방법인 순차 탐색을 알아보자
• 리스트 안에 있는 특정한 데이터를 찾기 위해 가장 앞에서부터 데이터를 하나씩 확인하는 방법이다
• 정렬되어 있지 않은 리스트에서 특정 값을 찾을 때 주로 사용한다
• 리스트 내에 많은 데이터가 있더라도 시간만 있다면, 원하는 데이터를 찾을 수 있다
• 따라서 데이터의 개수가 N개일 때, 최대 N번의 비교 연산이 필요하므로, 최악의 경우 시간 복잡도는 O(N)이다

• 위와 같은 리스트에서 짱구를 찾을 때, 순차 탐색에서는 먼저 첫 번째 순서인 유리를 확인한다
• 짱구가 아니므로 그다음인 철수를 확인하고, 그다음으로 넘어가 짱구를 찾는다

 

순차 탐색 구현

# 순차 탐색 구현

# n:arr길이
# target:찾을데이터
# arr:리스트

def seq_search(n, target, arr):
	# for문으로 원소를 하나씩 확인
	for i in range(n):
		if arr[i] == targer:
			return i + 1

 

 

이진 탐색(Binary Search)

• 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다
• 데이터가 무작위인 경우 사용할 수 없으나 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다
• 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다
• 이진 탐색은 위치를 나타내는 변수 3개를 사용한다.
• 탐색하고자 하는 범위의 시작점(start), 끝점(mid) 그리고 중간점(center)이다
• 이진 탐색은 찾으려는 데이터와 중간 지점의 데이터를 반복적으로 비교해서 원하는 데이터를 찾아간다

• mid는 start와 end를 합쳐 반으로 나눈 값을 사용한다. 만약 소수인 경우, 소수점 이하는 버린다
• 이진 탐색은 확인할 때마다 원소의 개수가 평균적으로 절반이 줄어드므로, 시간 복잡도는 O(logN)이다
• 이진 탐색은 재귀 함수를 사용하거나 단순하게 반복문을 사용해 구현할 수 있다

 

재귀 함수를 사용한 이진 탐색 구현

def binary_search(arr, targer, start, end):
	if start > end:
		return None
	mid = (start+end) / 2
	if arr[mid] == target:
		return mid
	elif arr[mid] > target:
		return binary_search(arr, target, start, mid-1)
	else:
		return binary_search(arr, target, mid+1, end)

 

반복문을 사용한 이진탐색 구현

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