0428 알고리즘 1일차(~04)

선형 검색

선형에서 데이터를 찾는다.

*보초법 : 데이터에 가장 마지막에 내가 찾으려는 값을 추가해서 찾는 과정을 간략화
(마지막에 찾아지면 그 값은 못찾은것)

nums = [4,7,10,2,4,7,0,2,7,3,9]
print(f'nums: {nums}')
print(f'nums length : {len(nums)}')

searchData = int(input('input search number: '))
searchResulIdx = -1

nums.append(searchData)

n=0

while True:

    if nums[n] == searchData:
        if n != len(nums)-1:
            searchResulIdx = n
        break
    n+=1

print(f'nums: {nums}')
print(f'nums length : {len(nums)}')
print(f'searchResultIdx : {searchResulIdx}')

nums = [4,7,10,2,4,7,0,2,7,3,9]
print(f'nums: {nums}')
print(f'nums length : {len(nums)}')

searchData = int(input('input search number: '))
searchResultIdx = []

nums.append(searchData)
n=0
while True:
    if nums[n] == searchData:
        if n != len(nums)-1: #n번째 숫자 = 찾는 숫자 인 경우 중 
                            # 가장 마지막 번째가 같다는건 보초법으로 
                            만들어놓은 숫자랑 같다는 것이므로 그걸 빼주기 위한 것
            searchResultIdx.append(n)
        else:
            break
    n+=1

print(f'nums: {nums}')
print(f'nums length : {len(nums)}')
print(f'searchResultIdx :{searchResultIdx}')
print(f'searchResultIdx :{len(searchResultIdx)}')

이진 검색

정렬되어있는 자료구조에서 중앙값과의 크고 작음을 이용해서 데이터를 검색

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

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

staIdx = 0
endIdx = len(datas)-1
midIdx = (staIdx+endIdx)//2
midval = datas[midIdx]

print(midIdx,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]

    elif searchData < midval:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midval = datas[midIdx]

    elif searchData == midval:
        searchResultIdx = midIdx
        break
print(f'searchResultIdx: {searchResultIdx}')