선형 검색, 이진 검색

참고: 누구나 자료 구조와 알고리즘 2장,

모두를 위한 컴퓨터 과학(데이비드말란 교수님) 강의

 

1장에서는 배열이나 집합처럼 매우 유사해 보이는 두 자료 구조라도 효율성이 크게 다를 수 있음을 보았다.

 

2장에서는 어떤 자료 구조를 이미 결정했더라도 효율성에 영향을 미칠 수 있는 알고리즘에 대해 살펴본다.

알고리즘이란 단순히 어떤 문제를 풀어내기 위한 명령어 집합이다.

새 알고리즘을 분석하기 위해 자료 구조 하나를 살펴보자.

 

2.1. 정렬된 배열

정렬된 배열(ordered array)은 값이 항상 순서대로 있어야 한다. 일반 배열이 [8, 17, 3, 202] 일 때, 정렬된 배열은 [3, 17, 80, 202]라 할 수 있다. 정렬된 배열의 강력함은 검색 연산에서 드러난다.

 

전형적인 배열의 특정 값을 찾으려면 원하는 값을 찾을 때까지 왼쪽에서 오른쪽으로 한 번에 한 셀씩 확인하는 방법을 선형 검색 알고리즘 또는 순차 검색 알고리즘이라 불렀다. 선형 검색 알고리즘은 정확하지만 아주 효율적이지 못한 방법입니다. 자료가 정렬되어 있지 않거나, 그 어떤 정보도 없어 하나씩 찾아야 하는 경우에 유용합니다.

# 위키피디아 예시

def sequentialSearch(array, value):
	for i in range(len(array)):
		if array[i] == value:
			return i
	return False

[17, 3, 75, 80, 202]이라는 일반적인 배열에서 22라는 값을 찾으려면 22가 배열 어디든 있을 수 있으므로 모든 원소를 하나도 빠짐없이 검색해야 했다. 그러나 정렬된 배열 [3, 17, 75, 80, 202]에서 22를 찾는다고 하자. 75에 도달하면 더이상 22가 오른쪽에 있을 수 없으므로 바로 검색을 중단할 수 있다.

하지만 선형 검색보다 훨씬 뛰어난 알고리즘이 있다. 정렬된 배열이 전형적인 배열보다 크게 두드러진 장점은 이진 검색이라는 알고리즘을 쓸 수 있다는 점이다.

 

2.3. 이진 검색

오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 배열중간의 인덱스 값부터 시작하여, 찾고자 하는 값의 대소를 비교하여 탐색의 범위를 반으로 줄여나가는 방식이다.

def binary_search(data, search_value):
    start_index = 0				# 시작점 인덱스
    end_index = len(data)-1			# 끝점 인덱스
    
    while start_index <= end_index:
        mid = (start_index+end_index)//2        # //연산자는 나눗셈 후 소수점 이하를 버리고 몫만 구한다.
        if data[mid] == search_value:
            return mid
        elif data[mid] > search_value:
            end_index = mid-1
        elif data[mid] < search_value:
            start_index = mid+1
            
    # 시작점과 끝점 인덱스가 같아질 때까지 찾는 값이 없으면, None 반환        
    return None