Python - 알고리즘 (선형검색,이진검색)

선형검색

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.

datas = [3,2,5,7,9,1,0,8,6,4]

print(f'datas: {datas}')
print(f'datas length : {len(datas)}')

searchData = int(input('찾으려는 숫자 입력 : '))
searchResultIdx = -1

n = 0
while True:

if n == len(datas):
searchResultIdx = -1
break

elif datas[n] == searchData:
searchResultIdx = n
break

n += 1

print(f'searchResultIdx : {searchResultIdx}')

문제풀이 :
len(datas)까지 n이 계속 증가하면서 숫자를 찾는데 만약 len(datas)에 도달했다면
리스트에서 원하는 숫자를 찾지 못했다는 의미로 -1을 출력
만약 len(datas)범위 안에서 원하는 숫자 찾으면 그 숫자의 위치(인덱스) 출력

여기서
if n == len(nums):을 먼저 사용하는 이유는
n이 리스트의 길이와 같아지기전에 검사를 종료해야하기 떄문

for 문으로

• 중복숫자 인덱스 위치 뽑기

nums = [4,7,10,2,4,7,0,2,7,3,9]

n = 0

resultNums = []


Find = int(input('찾을 수 : '))

for i in range(len(nums)):

if Find == nums[i]:

print(nums[i])

resultNums.append(i)


print(resultNums)

이진검색

• 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
  (검색 범위를 점차 좁혀 나가면서 찾아나가는 방식)

datas = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # 정렬이 되어있다는 기본 전제하에 이진검색

print(f'datas: {datas}')
print(f'datas length : {len(datas)}')

searchData = int(input('search data: '))
searchResultIdx = -1


# 초기화
staIdx = 0
endIdx = len(datas) -1
midIdx = (staIdx + endIdx) // 2
midVal = datas[midIdx]

print(f'midIdx: {midIdx}') #중앙 인덱스값
print(f'midVal: {midVal}') # 중앙값

while searchData <= datas[len(datas)-1] and searchData >= datas[0]: # 범위밖으로 나가는거 막는거

​​​​if searchData == datas[len(datas)-1]: # 찾는값이 
​​​​​​​​searchResultIdx = len(datas) - 1
​​​​​​​​break

​​​​if searchData > midVal:
​​​​​​​​staIdx = midIdx
​​​​​​​​midIdx = (staIdx + endIdx) // 2
​​​​​​​​midVal = datas[midIdx]
​​​​​​​​print(f'midIdx: {midIdx}') #중앙 인덱스값
​​​​​​​​print(f'midVal: {midVal}') # 중앙값

​​​​elif searchData < midVal: #가운데값보다 작은경우 (데이터가 왼쪽)
​​​​​​​​endIdx = midIdx
​​​​​​​​midIdx = (staIdx +endIdx) // 2
​​​​​​​​midVal = datas[midIdx]
​​​​​​​​print(f'midIdx: {midIdx}') #중앙 인덱스값
​​​​​​​​print(f'midVal: {midVal}') # 중앙값


​​​​elif searchData == midVal:
​​​​​​​​searchResultIdx = midIdx
​​​​​​​​break

print(f'searchResult: {searchResultIdx}')

문제풀이 :

searchData <= datas[len(datas)-1] and searchData >= datas[0]:을 사용하여 범위를 지정해주고
midVal를 기준으로 나눠서 찾아나가는거