검색

검색의 개념

어떤 집합에서 원하는 것을 찾는 것

 

알고리즘의 종류

1. 순차검색

2. 이진 검색

 

#검색의 개념 :
    어떤 집합에서 원하는 개념을 찾는 것

 

#정렬되지 않은 집합의 순차 검색 원리와 구현
찾을 데이터를 집합의 맨 앞에서 부터 찾아가야한다
검색이 성공하는 경우 실패하는 경우로 나뉜다.

 

#클래스와 함수 선언 부분
#정렬되지 않은 데이터의 순차 검색
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, '위치에 있음')

*찾을 값을 입력하세요. --> 150
배열 --> [188, 150, 168, 162, 105, 120, 177, 50]
##비교한 데이터 ==> 188 150 
150 (은)는  1 위치에 있음

 

#정렬된 데이터의 순차 검색
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 = [180, 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, '위치에 있음')

*찾을 값을 입력하세요. --> 150
배열 --> [50, 105, 120, 150, 162, 168, 177, 180]
##비교한 데이터 ==> 50 105 120 150 
150 (은)는 3 위치에 있음

 

#이진 검색
시작 중앙 끝을 반복적으로 1/2씩 줄여가면서 계산하는 방식

 

#이진 검색의 구현
시작 = 0
끝 = 배열길이 - 1
while (시작 <= 끝)
    중앙 = (시작+끝) // 2
    if 찾는 값 == 중앙 :
        검색 성공. 중앙 위치 반환
    elif 찾는 값 > 중앙 :
        시작 = 중앙 + 1
    else :
        끝 = 중앙 - 1

while 문에서 중앙 위치를 반환하지 못하고, 여기까지 오면 실패

 

#정렬된 데이터의 이진 검색
#클래스와 함수 선언 부분
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, '위치에 있음')