[Do it! 자료구조, 알고리즘 Python] 3장. 검색 알고리즘

검색 : 어떤 조건을 만족하는 데이터를 찾아내는 것.

검색의 종류 : 배열 검색(선형검색, 이진 검색, 해시법), 연결 리스트 검색, 이진 검색 트리 검색

# while 문으로 작성한 선형 검색 알고르짐
>>> from typing import Any, Sequence
>>> def seq_search(a:Sequence, key:Any) -> int:  ##int는 왜 입력하는건지???
	i=0
	while True:
		if i ==len(a):
			return-1     #검색에 실패하여 -1을 반환
		if a[i] ==key:
			return i     #검색에 성공해 현재 검사한 배열의 인덱스를 반환
		i+=1

		
>>> if __name__='__main__':
	
SyntaxError: invalid syntax
>>> if __name__=='__main__':
	num=int(input('원소 수를 입력해라:'))     #num값을 입력받음
	x=[None]*num                            #원소수가 num인 배열을 생성
	for i in range(num):
		x[i]=int(input(f'x[{i}]:'))
	ky = int(input('검색할 값을 입력해라:'))   #검색할 키 ky를 입력받음
	idx=seq_search(x,ky)                     #ky와 값이 같은 원소를 x에서 검색
	if idx==-1:
		print('검색값을 갖는 원소가 존재하지 않는다')
	else:
		print(f'검색값은 x[{idx}]에 있다.')

		
원소 수를 입력해라:16
x[0]:2
x[1]:5
x[2]:8
x[3]:6
x[4]:4
x[5]:2
x[6]:1
x[7]:3
x[8]:9
x[9]:4
x[10]:5
x[11]:2
x[12]:7
x[13]:6
x[14]:2
x[15]:4
검색할 값을 입력해라:6
검색값은 x[3]에 있다.

#for문으로 작성한 선형 검색 알고리즘 -> while문 대신 for문으로 작성하면 코드 더 짧고 간결해짐.
>>> from typing import Any, Sequence
>>> def seq_search(a:Sequence, key:Any) -> int:
	for i in range(len(a)):
		if a[i] ==key:
			return i #검색 성공(인덱스 반환)
	return -1 #검색 실패(-1을 반환)

>>> if __name__=='__main__':
	num=int(input('원소 수를 입력해라:'))
	x=[None]*num
	for i in range(num):
		x[i]=int(input(f'x[{i}]:'))
	ky = int(input('검색할 값을 입력해라:'))
	idx=seq_search(x,ky)
	if idx==-1:
		print('검색값을 갖는 원소가 존재하지 않는다')
	else:
		print(f'검색값은 x[{idx}]에 있다.')

		
원소 수를 입력해라:7
x[0]:5
x[1]:7
x[2]:4
x[3]:2
x[4]:6
x[5]:9
x[6]:3
검색할 값을 입력해라:7
검색값은 x[1]에 있다.

# 선형 검색 알고리즘을 보초법으로 수정
>>> from typing import Any, Sequence
>>> import copy
>>> def seq_search(seq: Sequence, key:Any) -> int:
	a=copy.deepcopy(seq) #seq를 복사
	a.append(key)  #보초 key를 추가
	i=0
	while True:
		if a[i] ==key:
			break  #검색에 성공하면 while문 종료
		i+=1
	return -1 if i ==len(seq) else i

>>> if __name__ == '__main__':
	num = int(input('원소 수를 입력:')) #num값 입력
	x=[None]*num #원소 수가 num인 배열을 생성
	for i in range(num):
		x[i] = int(input(f'x[{i}]:'))
	ky = int(input('검색할 값 입력:')) #검색할 키 ky를 입력받기
	idx = seq_search(x,ky) #키 ky값과 같은 원소를 x에서 검색
	if idx == -1:
		print('검색값을 갖는 원소가 존재하지 않는다.')
	else:
		print(f'검색값은 x[{idx}]에 있따')

		
원소 수를 입력:7
x[0]:4
x[1]:6
x[2]:8
x[3]:2
x[4]:9
x[5]:1
x[6]:5
검색할 값 입력:3
검색값을 갖는 원소가 존재하지 않는다.

# 이진 검색 알고리즘
>>> from typing import Any, Sequence
>>> def bin_search(a:Sequence, key:Any) -> int:
	pl=0 # 검색 범위 맨 앞 원소의 인덱스
	pr=len(a)-1 #검색 범위 맨 끝 원소의 인덱스
	while True:
		pc=(pl+pr) // 2 #중앙 원소의 인덱스
		if a[pc] == key:
			return pc #검색 성공
		elif a[pc] < key:
			pl = pc+1 #검색 범위를 뒤쪽 절반으로 좁힘
		else:
			pr =pc-1 #검색 범위를 앞쪽 절반으로 좁힘
		if pl>pr:
			break
	return -1  #검색 실패

>>> if __name__ == '__main__':
	num=int(input('원소 수를 입력:'))
	x=[None]*num #원소수가 num인 배열을 생성
	print('배열 데이터를 오름차순으로 입력해라.')
	x[0] = int(input('x[0]:'))
	for i in range(1, num):
		while True:
			x[i] = int(input(f'x[{i}]:'))
			if x[i] >= x[i-1]:  #바로 직전에 입력한 원소값보다 큰 값 입력
				break
	ky=int(input('검색할 값 입력:')) #검색할 키값 ky 입력
	idx = bin_search(x,ky) #ky값과 같은 원소를 x에서 검색
	if idx== -1:
		print('검색값을 갖는 원소가 없다')
	else:
		print(f'검색값은 x[{idx}]에 있따')

		
원소 수를 입력:7
배열 데이터를 오름차순으로 입력해라.
x[0]:1
x[1]:2
x[2]:4
x[3]:5
x[4]:6
x[5]:7
x[6]:8
검색할 값 입력:5
검색값은 x[3]에 있따
>>>

3-4. 해시

해시법 : 데이터를 저장할 위치=인덱스 를 간단한 연산으로 구하는 것, 원소 검색 , 추가/삭제 가능