선형검색

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

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

seachData = int(input('숫자 입력 : '))
searchIdx = -1

n = 0
while True:

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

    elif datas[n] == seachData:
        searchIdx = n
        break

    n += 1

print(searchIdx)

보초법

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

이진검색

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

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
print(nums)
print(len(nums))

searchData = int(input('input search : '))
searchIdxs = -1

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

print(midIdx)
print(midVal)


while searchData <= nums[len(nums)-1] and searchData >= nums[0]:

    if searchData == nums[len(nums)-1]:
        searchIdxs = len(nums) - 1
        break

    if searchData > midVal:
        staIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(midIdx)
        print(midVal)

    elif searchData < midVal:
        endIdx = midIdx
        midIdx = (staIdx + endIdx) // 2
        midVal = nums[midIdx]
        print(midIdx)
        print(midVal)
    
    elif searchData == midVal:
        searchIdxs = midIdx
        break

print(searchIdxs)

순위

수의 크고 작음을 이용해서 수의 순서를 정하는 것

import random

nums = random.sample(range(50,101), 20)
ranks = [0 for i in range(20)]

print(f'nums : {nums}')
print(f'ranks : {ranks}')

for idx, num1 in enumerate(nums):
    for num2 in nums:
        if num1 < num2:
            ranks[idx] += 1

print(f'nums : {nums}')
print(f'ranks : {ranks}')

for idx, num in enumerate(nums):
    print(f'num : {num} \t rank: {ranks[idx] + 1}')
    
nums : [79, 54, 82, 65, 91, 57, 87, 98, 92, 97, 59, 56, 69, 100, 90, 73, 94, 70, 76, 86]
ranks : [10, 19, 9, 15, 5, 17, 7, 1, 4, 2, 16, 18, 14, 0, 6, 12, 3, 13, 11, 8]
num : 79         rank: 11
num : 54         rank: 20
num : 82         rank: 10
num : 65         rank: 16
num : 91         rank: 6
num : 57         rank: 18
num : 87         rank: 8
num : 98         rank: 2
num : 92         rank: 5
num : 97         rank: 3
num : 59         rank: 17
num : 56         rank: 19
num : 69         rank: 15
num : 100        rank: 1
num : 90         rank: 7
num : 73         rank: 13
num : 94         rank: 4
num : 70         rank: 14
num : 76         rank: 12
num : 86         rank: 9

이글은 제로베이스 데이터 취업스쿨의 강의자료 일부를 발췌하여 작성되었습니다.