33
loading...
Search algorithms.
Search algorithms are some of the most popular algorithms that we use in our everyday lives. There are two types of search algorithms:
Linear search
Binary search
One of the simplest search algorithms. Linear search algorithms are sequential algorithms which involve traversing of a sequence of values such as a list or an array, from the beginning to the end until a match has been found or to the end of the list. If the search is successful i.e if the element is located the algorithm will return the index of the element, however if the element cannot be located the algorithm will return -1.
The linear search algorithm can be applied to both sorted and unsorted lists.
Linear search algorithms have a time complexity of O(N) which implies that time is linearly dependent on the size of the array/list.
Very simple to implement.
Linear search algorithms have a time complexity of O(N) which implies that time is linearly dependent on the size of the array/list.
Very simple to implement.
def linear_search(array, x, n):
for i in range(0, n):
if array[i] == x:
return i
return -1
#implementation
array =[23, 45, 12, 90, 34, 7]
x = 34
n = len(array)
result = linear_search(array, x, n)
if result == -1:
print("Element is not present in the array!")
else:
print("Element is present in the array !")Output:
Element is present in the array !Unlike Linear Search algorithm the Binary search algorithm can only be used if the elements of a list or array are sorted.
Step 1. We first need to determine if the elements of that list are sorted.
Step 2. If so compare the element with the element in the middle of the array/list
Step 3. If the element matches with the elements in the middle of the array/list return the index of the element.
Step 4. Otherwise determine if the element you’re searching for is greater or less than the element in the middle of the list/array.
Step 5. if the element is greater than the element in the middle of the list/array pick the elements to the right and start from step 1 again.
Step 6. If the element to be searched is less than the element of in the middle of the elements to the left pick element on the left and begin again from step 1.
Unlike the Linear search algorithm the binary search algorithm is very useful in cases where Lists/ arrays contain very large elements. However, the list/array in question needs to be sorted beforehand.
It is particularly good for searching through very large lists/arrays.
It has a time complexity of O(Log N).
The Binary search can be Implemented in two ways:
It has a time complexity of O(Log N).
The Binary search can be Implemented in two ways:
Iterative Method.
Recursive Method.
The recursive method of implementing the binary search follows the divide and conquer approach while the iterative method doesn’t. Both of these methods can be implemented as shown below.
Iterative Implementation of the Binary Search.
def binary_search(array, x, low, high):
while low <= high:
mid = low + (high - low)//2
if array[mid] == x:
return mid
elif array[mid] < x:
low = mid +1
else:
high = mid -1
return -1
#implementation of the algorithm
array = [12, 13, 15, 17, 28, 88, 90, 99]
x = 28
index = binary_search(array, x, 0, len(array)-1)
if index != -1:
print("Element can be found at Index: " +str(index))
else:
print("Element cannot be found !")Output:
Element can be found at Index: 4def binary_search(array, x, low, high):
if high >= low:
mid = low + (high - low)//2
if array[mid] == x:
return mid
elif array[mid] > x:
return binary_search(array, x, low, mid-1)
else:
return binary_search(array, x, mid + 1, high)
return -1
#implementation of the algorithm
array = [12, 67, 77, 79, 88, 90]
x = 79
result_index = binary_search(array, x, 0, len(array)-1)
if result_index != -1:
print("The element in the array can be found at index: " +str(result_index))
else:
print("Element cannot be found in the array !")Output:
The element in the array can be found at index: 333