[검색] 선형검색 알고리즘

1. 선형검색

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

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

 3   2   5   7   9   1   0   8   6   4

데이터가 위와 같은 경우 인덱스 0부터 9까지 순차적으로 검색한다.

검색 성공 : 원하는 데이터가 9인 경우 [0] [1] [2] [3] [4]를 훑고 찾는다

검색 실패 : 원하는 데이터가 없는 경우

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('searchResultIdx:', searchResultIdx)

2. 보초법

선형검색에서 약간 수정한 방법

마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.

만약 찾는 숫자가 9인 경우

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

 3   2   5   7   9   1   0   8   6   4    9

데이터가 위와 같은 경우 인덱스 0부터 9까지 순차적으로 검색한다.

검색 성공 : 마지막 이전에 '9'가 검색된 경우

검색 실패 : 마지막에 '9'가 검색된 경우

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

#선형검색과 다른 부분
datas.append(searchData)

n = 0
while True:

    if datas[n] == searchData:
        if n != len(datas)-1:
            searchResultIdx = n
        break

    n += 1

print('searchResultIdx:', searchResultIdx)
print('n', n)