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를 더 간단하게 구현할 수도 있습니다.