Ch13 Lab - 검색

📘 교재 예제 (Code)

📘 Textbook Examples (Code)

Code13-01.py

순차 검색 알고리즘을 구현합니다

## 함수 선언 부분 ## 
def seqSearch(ary, fData) :

	pos = -1
	size = len(ary)
	print('## 비교한 데이터 ==> ', end = '')
	for i in range(size) :
		print(ary[i], end = ' ')
		if ary[i] == fData :
			pos = i
			break
	print()
	return pos

## 전역 변수 선언 부분 ## 
dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = 0

## 메인 코드 부분 ##

findData = int(input('* 찾을 값을 입력하세요. --> '))
print('배열 -->', dataAry)
position = seqSearch(dataAry, findData)
if position == -1 :
	print(findData, '(이)가 없네요.')
else :
	print(findData,'(은)는 ', position, '위치에 있음')

Code13-01.py

Implements the sequential (linear) search algorithm

## Function Declarations ## 
def seqSearch(ary, fData) :

	pos = -1
	size = len(ary)
	print('## Compared data ==> ', end = '')
	for i in range(size) :
		print(ary[i], end = ' ')
		if ary[i] == fData :
			pos = i
			break
	print()
	return pos

## Global Variables ## 
dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = 0

## Main Code ## 
findData = int(input('* Enter value to search. --> '))
print('Array -->', dataAry)
position = seqSearch(dataAry, findData)
if position == -1 :
	print(findData, ' not found.')
else :
	print(findData,' is at ', position, 'position(s)')

Code13-02.py

정렬된 배열에서 순차 검색을 개선합니다

## 함수 선언 부분 ## 
def seqSearch(ary, fData) :

	pos = -1
	size = len(ary)
	print('## 비교한 데이터 ==> ', end = '')
	for i in range(size) :
		print(ary[i], end = ' ')
		if ary[i] == fData :
			pos = i
			break
		elif ary[i] > fData :
			break
	print()
	return pos

## 전역 변수 선언 부분 ## 
dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = 0

## 메인 코드 부분 ##

dataAry.sort()
findData = int(input('* 찾을 값을 입력하세요. --> '))
print('배열 -->', dataAry)
position = seqSearch(dataAry, findData)
if position == -1 :
	print(findData, '(이)가 없네요.')
else :
	print(findData, '(은)는 ', position, '위치에 있음')

Code13-02.py

Improves sequential search on a sorted array

## Function Declarations ## 
def seqSearch(ary, fData) :

	pos = -1
	size = len(ary)
	print('## Compared data ==> ', end = '')
	for i in range(size) :
		print(ary[i], end = ' ')
		if ary[i] == fData :
			pos = i
			break
		elif ary[i] > fData :
			break
	print()
	return pos

## Global Variables ## 
dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = 0

## Main Code ## 
dataAry.sort()
findData = int(input('* Enter value to search. --> '))
print('Array -->', dataAry)
position = seqSearch(dataAry, findData)
if position == -1 :
	print(findData, ' not found.')
else :
	print(findData, ' is at ', position, 'position(s)')

Code13-03.py

이진 검색 알고리즘을 구현합니다

## 함수 선언 부분 ## 
def binSearch(ary, fData) :

	pos = -1
	start = 0
	end = len(ary) - 1

	while (start <= end) :
		mid = (start + end ) // 2
		if fData == ary[mid] :
			return mid
		elif fData > ary[mid] :
			start = mid + 1
		else :
			end = mid - 1

	return pos

## 전역 변수 선언 부분 ##
dataAry = [ 50, 60, 105, 120, 150, 160, 162, 168, 177, 188]
findData = 162	# 할머니키

## 메인 코드 부분 ##

print('배열 -->', dataAry)
position = binSearch(dataAry, findData)
if position == -1 :
	print(findData,'(이)가 없네요.')
else :
	print(findData,'(은)는 ', position, '위치에 있음')

Code13-03.py

Implements the binary search algorithm

## Function Declarations ## 
def binSearch(ary, fData) :

	pos = -1
	start = 0
	end = len(ary) - 1

	while (start <= end) :
		mid = (start + end ) // 2
		if fData == ary[mid] :
			return mid
		elif fData > ary[mid] :
			start = mid + 1
		else :
			end = mid - 1

	return pos

## Global Variables ##
dataAry = [ 50, 60, 105, 120, 150, 160, 162, 168, 177, 188]
findData = 162	# GrandmaHeight

## Main Code ##
print('Array -->', dataAry)
position = binSearch(dataAry, findData)
if position == -1 :
	print(findData,' not found.')
else :
	print(findData,' is at ', position, 'position(s)')

Code13-04.py

인덱스 테이블을 만들어 검색 성능을 개선합니다

from  operator import itemgetter

## 함수 선언 부분 ## 
def makeIndex(ary, pos) :

	beforeAry = []
	index = 0
	for data in ary :
		beforeAry.append( (data[pos], index) )
		index += 1

	sortedAry = sorted(beforeAry, key = itemgetter(0))
	return sortedAry

def bookSearch(ary, fData) :

	pos = -1
	start = 0
	end = len(ary) - 1

	while (start <= end) :
		mid = (start + end ) // 2
		if fData == ary[mid][0] :
			return ary[mid][1]
		elif fData > ary[mid][0] :
			start = mid + 1
		else :
			end = mid - 1

	return pos

## 전역 변수 선언 부분 ##
bookAry = [['어린왕자', '쌩떽쥐베리'],['이방인', '까뮈'], ['부활', '톨스토이'],
		   ['신곡', '단테'], ['돈키호테', '세르반테스'], ['동물농장', '조지오웰'],
		   ['데미안','헤르만헤세'], ['파우스트', '괴테'], ['대지', '펄벅']]
nameIndex = []
authIndex = []

## 메인 코드 부분 ##

print('#책장의 도서 ==>', bookAry)
nameIndex = makeIndex(bookAry, 0)
print('#도서명 색인표 ==>', nameIndex)
authIndex = makeIndex(bookAry, 1)
print('#작가명 색인표 ==>', authIndex)

findName = '신곡'
findPos = bookSearch(nameIndex, findName)
if findPos != -1 :
	print(findName, '의 작가는', bookAry[findPos][1], '입니다.')
else :
	print(findName, ' 책은 없습니다.')

findName = '괴테'
findPos = bookSearch(authIndex, findName)
if findPos != -1 :
	print(findName, '의 도서는', bookAry[findPos][0], '입니다.')
else :
	print(findName, ' 작가는 없습니다.')

Code13-04.py

Creates an index table to improve search performance

from  operator import itemgetter

## Function Declarations ## 
def makeIndex(ary, pos) :

	beforeAry = []
	index = 0
	for data in ary :
		beforeAry.append( (data[pos], index) )
		index += 1

	sortedAry = sorted(beforeAry, key = itemgetter(0))
	return sortedAry

def bookSearch(ary, fData) :

	pos = -1
	start = 0
	end = len(ary) - 1

	while (start <= end) :
		mid = (start + end ) // 2
		if fData == ary[mid][0] :
			return ary[mid][1]
		elif fData > ary[mid][0] :
			start = mid + 1
		else :
			end = mid - 1

	return pos

## Global Variables ##
bookAry = [['LittlePrince', 'SaintExupery'],['TheStranger', 'Camus'], ['Resurrection', 'Tolstoy'],
		   ['new song', 'Dante'], ['DonQuixote', 'Cervantes'], ['AnimalFarm', 'GeorgeOrwell'],
		   ['Demian','HermannHesse'], ['Faust', 'Goethe'], ['TheGoodEarth', 'PearlBuck']]
nameIndex = []
authIndex = []

## Main Code ##
print('#Books on shelf ==>', bookAry)
nameIndex = makeIndex(bookAry, 0)
print('#Book title index table ==>', nameIndex)
authIndex = makeIndex(bookAry, 1)
print('#Author name index table ==>', authIndex)

findName = 'new song'
findPos = bookSearch(nameIndex, findName)
if findPos != -1 :
	print(findName, ''s author is', bookAry[findPos][1], '.')
else :
	print(findName, ' Book not found.')

findName = 'Goethe'
findPos = bookSearch(authIndex, findName)
if findPos != -1 :
	print(findName, ''s books are', bookAry[findPos][0], '.')
else :
	print(findName, ' Author not found.')

📗 응용 예제 (Ex)

📗 Applied Examples (Ex)

Ex13-01.py

검색 응용: 대용량 데이터에서 이진 검색 실습

import random

## 함수 선언 부분 ##
def binSearch(ary, fData) :

	start = 0
	end = len(ary) - 1

	while (start <= end) :
		mid = (start + end) // 2
		if fData == ary[mid] :
			return mid
		elif fData > ary[mid] :
			start = mid + 1
		else :
			end = mid - 1

	return -1

## 전역 변수 선언 부분 ##
dataAry = ['바나나맛우유', '레쓰비캔커피', '츄파춥스', '도시락', '삼다수', '코카콜라', '삼각김밥']
sellAry = [ random.choice(dataAry) for _ in  range(20)]

## 메인 코드 부분 ##

print('#오늘 판매된 전체 물건(중복O, 정렬X) -->', sellAry)
sellAry.sort()
print('#오늘 판매된 전체 물건(중복O, 정렬O) -->', sellAry)
sellProduct = list(set(sellAry))
print('#오늘 판매된 물품 종류(중복x) -->', sellProduct)

countList = []
for product in sellProduct :
	count = 0
	pos = 0
	while (pos != -1) :
		pos = binSearch(sellAry, product)
		if pos != -1 :
			count += 1
			del(sellAry[pos])
	countList.append( (product, count))

print()
print("결산 결과 ==>", countList)

Ex13-01.py

Search application: binary search on large datasets

import random

## Function Declarations ##
def binSearch(ary, fData) :

	start = 0
	end = len(ary) - 1

	while (start <= end) :
		mid = (start + end) // 2
		if fData == ary[mid] :
			return mid
		elif fData > ary[mid] :
			start = mid + 1
		else :
			end = mid - 1

	return -1

## Global Variables ##
dataAry = ['BananaMilk', 'LetsBeCoffee', 'ChupaChups', 'Lunchbox', 'Samdasu', 'CocaCola', 'Onigiri']
sellAry = [ random.choice(dataAry) for _ in  range(20)]

## Main Code ##
print('#All items sold today (dupl., unsorted) -->', sellAry)
sellAry.sort()
print('#All items sold today (dupl., sorted) -->', sellAry)
sellProduct = list(set(sellAry))
print('#Item types sold today (no duplicates) -->', sellProduct)

countList = []
for product in sellProduct :
	count = 0
	pos = 0
	while (pos != -1) :
		pos = binSearch(sellAry, product)
		if pos != -1 :
			count += 1
			del(sellAry[pos])
	countList.append( (product, count))

print()
print("settlement result ==>", countList)

Ex13-02.py

검색 응용: 순차 검색과 이진 검색의 성능을 비교합니다

import random

## 함수 선언 부분 ##
def seqSearch(ary, fData) :

	global count
	pos = -1
	for i in range(len(ary)) :
		count += 1
		if ary[i] == fData :
			pos = i
			break
	return pos

def binSearch(ary, fData) :

	global count
	start = 0
	end = len(ary) - 1

	while (start <= end) :
		count += 1
		mid = (start + end) // 2

		if fData == ary[mid] :
			return mid
		elif fData > ary[mid] :
			start = mid + 1
		else :
			end = mid - 1

	return -1

## 전역 변수 선언 부분 ##
dataAry, sortedAry = [], []
findData = 7878
count = 0

## 메인 코드 부분 ##

dataAry = [ random.randint(0, 999999) for _ in range(1000000)]
dataAry.insert(random.randint(0, 1000000), findData)
sortedAry = sorted(dataAry)

print('#비정렬 배열(100만개) -->', dataAry[0:5], '~~~~', dataAry[-5:len(dataAry)])
print('#정렬 배열(100만개) -->', sortedAry[0:5], '~~~~', sortedAry[-5:len(sortedAry)])

count =0
pos = seqSearch(dataAry,findData)
if pos != -1 :
	print('순차 검색(비정렬 데이터) -->', count, '회')

count =0
pos = binSearch(sortedAry, findData)
if pos != -1 :
	print('이진 검색(정렬 데이터) -->', count, '회')

Ex13-02.py

Search application: compares sequential vs. binary search performance

import random

## Function Declarations ##
def seqSearch(ary, fData) :

	global count
	pos = -1
	for i in range(len(ary)) :
		count += 1
		if ary[i] == fData :
			pos = i
			break
	return pos

def binSearch(ary, fData) :

	global count
	start = 0
	end = len(ary) - 1

	while (start <= end) :
		count += 1
		mid = (start + end) // 2

		if fData == ary[mid] :
			return mid
		elif fData > ary[mid] :
			start = mid + 1
		else :
			end = mid - 1

	return -1

## Global Variables ##
dataAry, sortedAry = [], []
findData = 7878
count = 0

## Main Code ##
dataAry = [ random.randint(0, 999999) for _ in range(1000000)]
dataAry.insert(random.randint(0, 1000000), findData)
sortedAry = sorted(dataAry)

print('#Unsorted array (1M items) -->', dataAry[0:5], '~~~~', dataAry[-5:len(dataAry)])
print('#Sorted array (1M items) -->', sortedAry[0:5], '~~~~', sortedAry[-5:len(sortedAry)])

count =0
pos = seqSearch(dataAry,findData)
if pos != -1 :
	print('Sequential search (unsorted data) -->', count, 'times')

count =0
pos = binSearch(sortedAry, findData)
if pos != -1 :
	print('Binary search (sorted data) -->', count, 'times')

📙 자가 실습 (Self)

📙 Self Practice (Self)

Self13-01.py

순차 검색으로 모든 위치를 찾는 함수를 직접 구현합니다

## 함수 선언부
def seqSearch(ary, fData) :

    posList = []
    size = len(ary)
    for i in range(size) :
        if ary[i] == fData :
            posList.append(i)
    return posList

## 전역 변수부
dataAry = [188, 50, 150, 168, 50, 162, 105, 120, 177, 50]
findData = 50

## 메인 코드부

print('배열 -->', dataAry)
positionList = seqSearch(dataAry, findData)
if positionList == [] :
    print(findData,'(이)가 없네요.')
else :
    print(findData,'(은)는 ', positionList, '위치에 있음')

Self13-01.py

Implements a function to find all positions using sequential search yourself

## Function Declarations
def seqSearch(ary, fData) :

    posList = []
    size = len(ary)
    for i in range(size) :
        if ary[i] == fData :
            posList.append(i)
    return posList

## Global Variables
dataAry = [188, 50, 150, 168, 50, 162, 105, 120, 177, 50]
findData = 50

## Main Code
print('Array -->', dataAry)
positionList = seqSearch(dataAry, findData)
if positionList == [] :
    print(findData,' not found.')
else :
    print(findData,' is at ', positionList, 'position(s)')

Self13-02.py

이진 검색을 직접 구현하고 비교 횟수를 셉니다

import random
## 함수 선언부
def binSearch(ary, fData) :

    global  count
    pos = -1
    start = 0
    end = len(ary) - 1

    while (start <= end) :
        count += 1
        mid = (start + end ) // 2
        if fData == ary[mid] :
            return mid
        elif fData > ary[mid] :
            start = mid + 1
        else :
            end = mid - 1

    return pos

## 전역 변수부
dataAry = [ ]
findData =  0
count = 0

## 메인 코드부

dataAry = [random.randint(0,100000) for _ in range(100000)]
dataAry.sort()
findData = random.randint(0,100000)
print('배열일부 -->', dataAry[:5], '~~~~', dataAry[-6:-1])
position = binSearch(dataAry, findData)
if position == -1 :
    print(findData,'(이)가 없네요.')
else :
    print(findData,'(은)는 ', position, '위치에 있음')
print('##', count, "회 검색함")