Algorithms 1 - Linear and Binary Search
June 1, 2024
1 Day 31
Practicing Python From Basics
1.1 Linear Search:
• Linear search, also known as sequential search, checks each element in a collection one by one
until the target element is found or the end of the collection is reached.
• It’s a simple but inefficient algorithm, especially for large datasets, as it has a time com-
plexity of O(n) in the worst case.
• Linear search is applicable to both sorted and unsorted collections.
1.1.1 Implementation
[6]: def linear_search(key,arr):
for index in range(len(arr)):
if arr[index] == key:
return index
return 0
1.1.2 Calling function
[7]: arr = [5,8,2,10,3,6]
key = 3
result = linear_search(key,arr)
[8]: if result:
print(f'Element {key} found at index {result}')
else:
print("Element not found")
Element 3 found at index 4
1
1.1.3 2nd calling
[9]: key1 = 7
result1 = linear_search(key1,arr)
[11]: if result1:
print(f'Element {key1} found at index {result1}')
else:
print("Element not found")
Element not found
• The linear_search function takes a list arr and a target value key.
• It iterates through each element of the list using a for loop.
• For each element, it checks if it matches the target value.
• If a match is found, it returns the index of the element. If not found, it returns 0.
1.2 Binary Search
• Binary search is a more efficient algorithm for finding a target value within a sorted array.
• It repeatedly divides the search interval in half until the target is found or the interval is
empty.
• Binary search has a time complexity of O(log n), making it significantly faster than linear
search for large datasets.
• It requires the array to be sorted beforehand.
1.2.1 Implementation
[12]: def binary_search(key,arr):
start, end = 0, len(arr)-1
while start<=end:
mid = (start+end)//2
if arr[mid] == key:
return mid
elif arr[mid]<key:
start = mid+1
else:
end = mid-1
return 0
2
1.2.2 Calling Binary search
[13]: arr = [2, 4, 6, 8, 10, 12, 14, 16]
key = 12
result = binary_search(key,arr)
[14]: if result:
print(f'Element {key} found at index {result}')
else:
print("Element not found")
Element 12 found at index 5
1.2.3 2nd Calling
[15]: key = 1
result = binary_search(key,arr)
[16]: if result:
print(f'Element {key} found at index {result}')
else:
print("Element not found")
Element not found
• The binary_search function takes a sorted array arr and a target value key.
• It initializes start and end pointers to the start and end of the array, respectively.
• It repeatedly calculates the mid index and compares the element at mid with the key.
• Based on the comparison, it updates start or end pointers to narrow down the search interval.
• It continues until the target is found or the search interval is empty, returning the index of
the target or 0 if not found.
