Spaces:
Sleeping
Sleeping
File size: 3,640 Bytes
4a3f117 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 | SEARCHING ALGORITHMS
====================
--- Linear Search ---
Check every element one by one until the target is found.
Time: O(n). Space: O(1). Works on unsorted arrays.
def linear_search(arr, target):
for i, val in enumerate(arr):
if val == target:
return i
return -1
print(linear_search([5, 3, 8, 1, 9], 8)) # Output: 2
print(linear_search([5, 3, 8, 1, 9], 7)) # Output: -1
--- Binary Search ---
Works on SORTED arrays. Compare target with middle element.
If smaller, search left half. If larger, search right half.
Time: O(log n). Space: O(1) iterative, O(log n) recursive.
# Iterative
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7)) # Output: 3
print(binary_search(arr, 10)) # Output: -1
# Recursive
def binary_search_recursive(arr, target, low, high):
if low > high:
return -1
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, high)
else:
return binary_search_recursive(arr, target, low, mid - 1)
arr = [2, 4, 6, 8, 10, 12]
print(binary_search_recursive(arr, 10, 0, len(arr) - 1)) # Output: 4
--- Find First and Last Position ---
Find first and last occurrence of target in sorted array.
def find_first(arr, target):
low, high, result = 0, len(arr) - 1, -1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
result = mid
high = mid - 1 # keep searching left
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
def find_last(arr, target):
low, high, result = 0, len(arr) - 1, -1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
result = mid
low = mid + 1 # keep searching right
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return result
arr = [1, 2, 2, 2, 3, 4]
print(find_first(arr, 2)) # Output: 1
print(find_last(arr, 2)) # Output: 3
--- Search in Rotated Sorted Array ---
Array was sorted then rotated (e.g., [4,5,6,7,0,1,2]).
def search_rotated(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
if arr[low] <= arr[mid]: # left half sorted
if arr[low] <= target < arr[mid]:
high = mid - 1
else:
low = mid + 1
else: # right half sorted
if arr[mid] < target <= arr[high]:
low = mid + 1
else:
high = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # Output: 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # Output: -1
--- Square Root using Binary Search ---
Find integer square root of a number without using sqrt().
def sqrt_binary(n):
if n < 2:
return n
low, high, result = 1, n // 2, 0
while low <= high:
mid = (low + high) // 2
if mid * mid == n:
return mid
elif mid * mid < n:
result = mid
low = mid + 1
else:
high = mid - 1
return result
print(sqrt_binary(16)) # Output: 4
print(sqrt_binary(20)) # Output: 4 (floor)
|