Search Algorithms
1. Linear Search
- Definition: A simple search that scans each element in a list sequentially.
- Time Complexity: O(n).
- Steps:
- Iterate through the list.
- Compare each element with the target value.
- If found, return the index; otherwise, return "not found".
def linear_search(A, target):
for i in range(len(A)):
if A[i] == target: # found
return i
return "not found" # not found
# main
data = [6, 2, 5, 1, 7, 10, 9, 3]
print(linear_search(data, 1)) # success
print(linear_search(data, 4)) # failure
---------------------------------------
3
"not found"
2. Binary Search
- Definition: An efficient search for sorted lists by repeatedly dividing the search interval in half.
- Time Complexity: O(log n).
Iterative Binary Search
def binary_search(A, target):
low = 0
high = len(A) - 1
while low <= high:
mid = (low + high) // 2
if A[mid] == target: # found
return mid
elif A[mid] > target: # left half
high = mid - 1
else: # right half
low = mid + 1
return "not found"
# main
data = [1, 2, 3, 5, 6, 7, 9, 10]
print(binary_search(data, 7)) # success
print(binary_search(data, 8)) # failure
---------------------------------------
5
"not found"
Recursive Binary Search
def binary_searchr(A, target, low, high):
if low > high:
return -1 # not found
mid = (low + high) // 2
if A[mid] == target:
return mid
elif target < A[mid]:
return binary_searchr(A, target, low, mid - 1) # left half
else:
return binary_searchr(A, target, mid + 1, high) # right half
# main
data = [6, 8, 12, 17, 19]
print(binary_searchr(data, 17, 0, len(data)-1)) # success
print(binary_searchr(data, 13, 0, len(data)-1)) # failure
---------------------------------------
3
-1