정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 비교하여 데이터를 검색한다.
개념datas = [1,2,3,4,5,6,7,8,9,10,11]
searchData = int(input('찾으려는 숫자: '))
searchResultIdx = -1 # 찾은 인덱스를 넣어줄 변수 초기화
staIdx = 0 # 시작인덱스
endIdx = len(datas)-1 # 마지막 인덱스
midIdx = (staIdx + endIdx) // 2 # 중앙값 인덱스
midVal = datas[midIdx] # 중앙값에 해당하는 데이터값
while searchData <= datas[len(datas)-1] and searchData >= datas[0]: # 주어진 리스트 숫자의 범위 안에 있을 경우까지만 수행
if searchData == datas[endIdx]:
searchResultIdx = endIdx
break
elif searchData > midVal: # 중앙값보다 크다면
# 다시 스타트 인덱스와 마지막 인덱스를 정의해준다.
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
elif searchData < midVal: # 중앙값보다 작다면
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]
elif searchData == midVal:
searchResultIdx = midIdx
break
Python
복사
nums = [4,10,22,5,0,17,7,11,9,61,88]
nums.sort() # 이진검색은 일단 정렬부터
searchData = int(input('찾으려는 숫자: '))
searchResultIdx = -1 # 찾게된 숫자의 idx
staIdx = 0 # 시작 idx
endIdx = len(nums) -1 # 끝 idx
midIdx = (staIdx + endIdx) // 2 # 중위수 idx
midVal = nums[midIdx] # 중앙값
# 탐색 시작
while searchData <= nums[len(nums)-1] and searchData >= nums[0]: # 즉 찾으려는 숫자가 리스트 범위 내에 있을 경우
if searchData == nums[endIdx]:
searchResultIdx = endIdx
break
elif searchData > midVal: # 오른쪽만 탐색하면 된다.
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
elif searchData < midVal: # 왼쪽만 탐색하면 된다.
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]
elif searchData == midVal: # 찾는 숫자가 중앙값에 있을 경우
searchResultIdx = midIdx
break # 찾으면 break
print(f'searchResultIdx : {searchResultIdx}')
Python
복사
# binary.py
def binarySort(ns,sn):
ns.sort() # 이진검색은 일단 정렬부터
searchResultIdx = -1 # 찾게된 숫자의 idx
staIdx = 0 # 시작 idx
endIdx = len(ns) -1 # 끝 idx
midIdx = (staIdx + endIdx) // 2 # 중위수 idx
midVal = ns[midIdx] # 중위수 값
# 이진 탐색 시작
while sn <= ns[len(ns)-1] and sn >= ns[0]: # 즉 찾으려는 숫자가 리스트 범위 내에 있을 때까지만 수행
if sn == ns[len(ns)-1]: # 찾으려는 숫자가 끝에 있는 값과 동일할 경우
searchResultIdx = len(ns) - 1
break
if sn > midVal: # 찾으려는 숫자가 중앙값보다 오른쪽에 있을 경우
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = ns[midIdx]
print(f'+ staIdx: {staIdx} ,endIdx: {endIdx}')
print(f'+ midIdx: {midIdx} ,midVal: {midVal}')
elif sn < midVal: # 왼쪽만 탐색하면 된다.
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = ns[midIdx]
print(f'- staIdx: {staIdx} ,endIdx: {endIdx}')
print(f'- midIdx: {midIdx} ,midVal: {midVal}')
elif sn == midVal: # 찾는 숫자가 중앙값에 있을 경우
searchResultIdx = midIdx
break # 찾으면 break
return searchResultIdx
Python
복사
# 숫자로 이루어진 리스트에서 사용자가 입력한 숫자를 검색하는 모듈을 만들자
# 검색 모듈을 이진 검색을 이용한다
# 검색 과정을 로그로 출력하자
# 검색에 성공하면 해당 정수의 인덱스를 출력하고 검색 결과가 없다면 -1을 출력하자.
import binary
nums = [1, 2, 4, 6, 7, 8, 10, 11, 13, 15, 16, 17, 20, 21, 23, 24, 27, 28]
searchNum = int(input('검색할 숫자: '))
resultIdx = binary.binarySort(nums,searchNum)
print(f'nums : {nums}')
if resultIdx == -1: # 찾은 숫자가 없는 경우
print('No results Found')
print(f'search result Idx : {resultIdx}')
else:
print('>>> Search Result <<<')
print(f'Search Result Idx : {resultIdx} <<<')
print(f'Search Result value : {nums[resultIdx]}')
Python
복사
사용자가 9를 입력할 경우 무한 루프에 빠지게 된다. 마지막에 9의 위치는 8과 10 사이에 남아 값을 구하지 못하고 계속 8과 10사이에서 제자리 걸음하는 것을 확인할 수 있다.
이런 경우를 생각해서 알고리즘을 추가적으로 보완해주는 것이 필요하다.
즉, staIdx 와 endIdx 가 연달아 있는 범위로까지 좁혀졌을 때, 찾는 값이 둘 중에도 없을 경우다.
def binarySort(ns,sn):
ns.sort() # 이진검색은 일단 정렬부터
searchResultIdx = -1 # 찾게된 숫자의 idx
staIdx = 0 # 시작 idx
endIdx = len(ns) -1 # 끝 idx
midIdx = (staIdx + endIdx) // 2 # 중위수 idx
midVal = ns[midIdx] # 중위수 값
# 이진 탐색 시작
while sn <= ns[len(ns)-1] and sn >= ns[0]: # 즉 찾으려는 숫자가 리스트 범위 내에 있을 때까지만 수행
if sn == ns[len(ns)-1]: # 찾으려는 숫자가 끝에 있는 값과 동일할 경우
searchResultIdx = len(ns) - 1
break
if staIdx + 1 == endIdx: #시작인덱스와 끝 인덱스가 연달아 있을만큼 범위가 좁혀졌을 때
if ns[staIdx] != sn and ns[endIdx] != sn: # 둘 중에 찾는 값이 없다면
break
if sn > midVal: # 찾으려는 숫자가 중앙값보다 오른쪽에 있을 경우
staIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = ns[midIdx]
print(f'+ staIdx: {staIdx} ,endIdx: {endIdx}')
print(f'+ midIdx: {midIdx} ,midVal: {midVal}')
elif sn < midVal: # 왼쪽만 탐색하면 된다.
endIdx = midIdx
midIdx = (staIdx + endIdx) // 2
midVal = ns[midIdx]
print(f'- staIdx: {staIdx} ,endIdx: {endIdx}')
print(f'- midIdx: {midIdx} ,midVal: {midVal}')
elif sn == midVal: # 찾는 숫자가 중앙값에 있을 경우
searchResultIdx = midIdx
break # 찾으면 break
return searchResultIdx
Python
복사