search algorithm.py

search algorithms은 기본적으로 list에 저장해서 data를 찾는 것이 목적이에요!
크게 두 가지 방법이 있는데 linear, binary가 있습니다!

linear search

search를 하는 방법은 찾는 값을 해당 list의 인자들과 비교를 하고 있으면 해당 index를 반환하고 없으면 None을 반환한다고 생각하면 되겠네요.
여기서 또 ordered인지 아닌지에 따라 code가 살짝 다릅니다.

#unordered
#given target, test_list
for i in range(len(test_list)):
	if target == test_list[i]:
    	return i
return None

import random


def search(target, ordered_list):
    for i in range(len(ordered_list)):
        if target == ordered_list[i]:
            return i
        elif ordered_list[i] > target:
            return None
    return None

#without replacement
test = random.sample(range(1, 15), 10)
test.sort()
print(test)

_target = 11
result = search(_target, test)
if result is None:
    print('%s is not found.' % _target)
else:
    print(f'{_target} is at index {result}')

binary search

import random


def search(target, ordered_list):
    left = 0
    right = len(ordered_list) - 1
    while(left <= right):
        mid = (right + left) // 2
        if target > ordered_list[mid]:
            left = mid + 1
        elif target < ordered_list[mid]:
            right = mid - 1
        else:
            return mid
    return None


test = []
for _ in range(10):
    n = random.randint(1, 15)
    test.append(n)
test.sort()
print(test)


_target = 11
result = search(_target, test)
if result is None:
    print('%s is not found.' % _target)
else:
    print(f'{_target} is at index {result}')

그냥 간단하게 구현해보았어요. random module을 통해 간단한 test case와 핵심 code를 구현해보았어요. 음.. 다만 제가 짠 binary search의 경우 중복되는 항목이 있을 때 가장 빠른 index의 search를 보장하지는 않습니다!

bisect module을 이용해서 binary search를 더 간단하게 구현할 수도 있습니다.