# Search Algorithms
def linear_search(arr, target):
"""Linear Search: Find the index of target in the array (O(n))"""
for i, val in enumerate(arr):
if val == target:
return i # Return the index of the target
return -1 # Return -1 if the target is not found
def binary_search(arr, target):
"""Binary Search: Find the index of target in a sorted array (O(log n))"""
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Return the index of the target
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # Return -1 if the target is not found
# Sorting Algorithms
def merge_sort(arr):
"""Merge Sort: Sort the array (O(n log n))"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
"""Merge two sorted lists"""
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
def quick_sort(arr):
"""Quick Sort: Sort the array (O(n log n) on average, O(n^2) in the worst case)"""
if len(arr) <= 1:
return arr
pivot = arr[0]
left = [x for x in arr[1:] if x < pivot]
right = [x for x in arr[1:] if x >= pivot]
return quick_sort(left) + [pivot] + quick_sort(right)
def bubble_sort(arr):
"""Bubble Sort: Sort the array (O(n^2))"""
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j] # Swap elements
swapped = True
if not swapped:
break # If no elements were swapped, the list is sorted
return arr
# Example Usage
# Search algorithms
arr = [3, 2, 1, 5, 4]
target = 5
print(f"Linear Search: Target {target} is at index {linear_search(arr, target)}")
arr_sorted = [1, 2, 3, 4, 5]
target = 4
print(f"Binary Search: Target {target} is at index {binary_search(arr_sorted, target)}")
# Sorting algorithms
arr_to_sort = [5, 2, 9, 1, 5, 6]
print(f"Original Array: {arr_to_sort}")
# Merge Sort
sorted_arr_merge = merge_sort(arr_to_sort)
print(f"Merge Sort: {sorted_arr_merge}")
# Quick Sort
sorted_arr_quick = quick_sort(arr_to_sort)
print(f"Quick Sort: {sorted_arr_quick}")
# Bubble Sort
sorted_arr_bubble = bubble_sort(arr_to_sort)
print(f"Bubble Sort: {sorted_arr_bubble}")
