Question 1.Linear or Sequential Search¶
Look for a given value in an unsortedlist. Traverse through the list, if you find the given value then return the index postion and it it not found then return -1.
Shares one item at a time Does not jump at any time Time taken to search elements is proportional to the number of elements Complexity is O(n)
def linear_search(seq,x):
for i in range(len(seq)):
if seq[i] == x:
return i
return -1
lst1 = [1,2,6,7,12,14,56]
linear_search(lst1,15)
Question 2.¶
Step-by-step Binary Search Algorithm:
Compare x with the middle element. If x matches with the middle element, we return the mid index. Otherwise If x is greater than the mid element, then x can only lie in the right half of the list after the mid element. So we search in the right half. Otherwise (x is smaller) we search in the left half. Elements need to be sorted. Time complexity is O(log N) We basically ignore half of the elements just after one comparison.
def binary_search(seq, x):
low = 0
high = len(seq) - 1
while low <= high:
middle = low + (high-low)//2
mid_value = seq[middle]
if mid_value == x:
return middle
elif x < mid_value:
high = middle - 1
else:
low = middle + 1
return -1
seq=[2,3,4,5,6,7,8,9,10,12,13,14]
x = 12
print(binary_search(seq, x))
#Recursive binary search
def binarySearch2(seq, x, low, high):
if low <= high:
middle = (low + high) // 2
if seq[middle] == x:
return middle
elif x > seq[middle] : ## x is on the right side
return binarySearch2(seq, x, middle + 1, high)
else : ## x is on the left side
return binarySearch2(seq, x, low, middle - 1)
else:
return -1
def binarySearch_r(seq,x):
return binarySearch2(seq, x,0,len(seq) - 1)
seq=[2,3,4,5,6,7,8,9,10,12,13,14]
x = 4
print(binarySearch_r(seq, x))
my_sort([4,6,1,7])
# Sorts all integers
def my_sort(lst):
for i in range(len(lst)):
for j in range(i + 1, len(lst)):
if lst[i] > lst[j]:
lst[i], lst[j] = lst[j], lst[i]
print(lst)
a=5
b=6
print(a,b)
a,b = b,a
print(a,b)
my_sort(['s','a', 'b'])