1. 선형 검색

선형 검색
선형으로 나열되어 있는 데이터를 순차적으로 스캔하면서 원하는 값을 찾는다.
◾️ 차례대로 나열했을 때 찾는 데이터가 있다 ➡️ 검색 성공
◾️ 차례대로 나열했을 때 찾는 데이터가 없다 ➡️ 검색 실패

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

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

n=0

while True:

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

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

    n += 1

print(f'searchResultIdx : {searchResulIdx}')

---

보초법
마지막 인덱스에 찾으려는 값을 추가해서 찾는 과정을 간략화한다.
◾️ 마지막 이전에 찾고자 하는 값이 검색되었다 ➡️ 검색 성공
◾️ 마지막 이전에 찾고자 하는 값이 검색되지 않았다 ➡️ 검색 실패

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

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

n=0
searchResultIdx = -1
datas.append(searchData) # 마지막 인덱스에 찾고 싶은 값 추가

while True:

    if datas[n] == searchData:
        if n != len(datas) -1 : # 위와 비교할 때 elif를 안 써도 된다.
            searchResultIdx = n
        break

    n += 1

print(f'searchResultIdx : {searchResultIdx}')

---

실습

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

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

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

for i in range(len(nums)):
    if nums[i] == 7:
        print(f'7의 첫번째 위치(인덱스)는: {i}')
        break

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

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

seven = 0
seven_index=[]
for i in range(len(nums)):
    if nums[i] == 7:
        seven_index.append(i)
        seven += 1

print(f'7의 모든 위치는: {seven_index}')
print(f'7의 개수는 총: {seven}')

---

2. 이진검색

이진검색
정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색한다.
◾️ 찾고자 하는 데이터가 중앙값 보다 작다 ➡️ 왼쪽만 검색

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

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

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[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'searchResultIdx: {searchResultIdx}')

---

실습

리스트를 오름차순으로 정렬한 후 '7'을 검색하고 위치(인덱스)를 출력하자.
nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]

nums = [4, 10, 22, 5, 0, 17, 7, 11, 9, 61, 88]

nums.sort()

search_num = int(input('위치를 찾고자 하는 정수: '))

searchResultIdx = -1
staIdx = 0
endIdx = len(nums)-1
midIdx = (staIdx + endIdx) // 2
midVal = nums[midIdx]

while searchResultIdx <= len(nums) -1 :

    if midVal == search_num:
        print(f'{search_num}의 위치는: {midIdx}')
        break

    elif midVal > search_num:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]

    elif midVal < search_num:
        staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]