[알고리즘] 선형 검색

[선형 검색]

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
  검색 성공 : 인덱스 반환
  검색 실패 : -1 반환

datas = [3,2,5,7,9,1,0,8,6,4]
print(f'datas:{datas}')
print(f'len : {len(datas)}')

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

n=0
while True:
    if datas[n] == searchData: 
        searchResultIdx = n                      # 값을 찾으면 넣어준 뒤 break
        break
    n += 1
    if n == len(datas):                          # 끝까지 찾았는데 안보이면 break
        break
print(f'찾는 값의 인덱스는 {searchResultIdx} 입니다.')

'''
datas:[3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
len : 10
찾으려는 숫자 입력 : 0
찾는 값의 인덱스는 6 입니다.

datas:[3, 2, 5, 7, 9, 1, 0, 8, 6, 4]
len : 10
찾으려는 숫자 입력 : 50
찾는 값의 인덱스는 -1 입니다.
'''

---

[보초법] 

• .마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화 한다.
• 데이터를 찾다가, 찾으려는 값이 마지막에 발견된다면 이는 내가 임의로 넣은 값이기 때문에 찾은게 아니다.
  검색 성공 : 인덱스 반환
  검색 실패 : -1 반환

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

datas.append(searchData)                        # 마지막에 내가 찾는 값을 넣어준다.

n=0
while True :
    if datas[n] == searchData:                  # 값을 찾았을 때
        if n != len(datas)-1:                   # 마지막 값만 아니면 찾아낸 인덱스 넣어주고
            searchResultIdx = n
        break                                   # 마지막 값이면 그냥 break
    n += 1

print(f'찾는 값의 인덱스는 {searchResultIdx} 입니다.')

결과는 선형 검색 때와 같다.

 

 

보초법을 쓰자 코드가 아주 조금 짧아진거 같다.

 

---

[실습1] 리스트에서 가장 앞에 있는 숫자 7을 검색하고 위치 (인덱스)를 출력하자.

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

numbers = [4,7,10,2,4,7,0,2,7,3,9]
searchNum = int(input())
resultIdx = -1
idx = 0
numbers.append(searchNum)
while True :
    if numbers[idx] == searchNum:
        if idx != len(numbers)-1:
            resultIdx = idx
        break
    idx +=1
print(f'{resultIdx}에 위치해 있습니다.')

[실습2] 리스트에서 숫자 '7'을 모두 검색하고 각각의 위치 (인덱스)와 검색 개수를 출력하자.

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

numbers = [4,7,10,2,4,7,0,2,7,3,9]
searchNum = int(input())
resultIdx = []
idx = 0
numbers.append(searchNum)
while True :
    if numbers[idx] == searchNum:
        if idx != len(numbers)-1:
            resultIdx.append(idx)
        else : break
    idx +=1
print(f'{resultIdx}에 위치해 있습니다.\
그리고 {len(resultIdx)}개의 {searchNum}이 존재합니다.')

'''
7
[1, 5, 8]에 위치해 있습니다.그리고 3개의 7이 존재합니다.
'''