[알고리즘] 7. 이진 탐색과 선택 정렬

1. 이진 검색 Binary Search

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고, 검색을 계속 진행하는 방법
• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 함
• 과정

1. 리스트 중앙에 있는 원소를 고른다.
2. 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
3. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
4. 찾고자 하는 값을 찾을 때까지 1~3을 반복한다.

• 구현

-검색 범위의 시작점과 종료점을 이용해 검색을 반복수행한다.

-이진 검색의 경우, 자료의 삽입이나 삭제가 발생할 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.

def binarySearch(a, N, key): # key를 찾으면 인덱스, 실패하면 -1 반환
	start = 0
	end = N-1
	while start <= end:
		middle = (start+end) //2
		if a[middle] == key : #검색 성공
			return middle
		elif a[middle] > key : #찾는 값보다 크다면
			end = middle -1 # 왼쪽 구간 선택
		else : 
			start = middle + 1
	return -1

2. 선택 정렬

• 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택해 위치를 교환
• O(n제곱)
• 순서

1. 주어진 리스트 중에서 최소값 찾기
2. 그 값을 리스트의 맨 앞에 위치한 값과 교환하기
3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 1, 2를 반복

selection_sort(a[], n):
	for i : 0 -> n-2:
		a[i] ,..., a[n-1] 원소 중 최소값 a[k] 찾음
		a[i]와 a[k] 교환

def selection_sort(a, N):
	for i in range(N-1):
		min_idx = i
		for j in range(i+1, N):
			if a[min_idx] > a[j] :
				min_idx = k
		a[i], a[min_idx] = a[min_idx], a[i]

3. 셀렉션 알고리즘

• 저장되어있는 자료로부터 K번째로 큰, 혹은 작은 원소를 찾는 방법
• 최소, 최대, 혹은 중간값을 찾는 알고리즘을 뜻하기도 한다.
• K 번째로 작은 원소를 찾기

def select(arr, k):
	for i in range(0, k):
		min_index = i
		for j in range(i+1, len(arr)):
			 if arr[min_idx] > arr[j]:
				 min_index = j
		arr[i], arr[min_idx] = arr[min_idx], arr[i]
	return arr[k-1]