Introduction to Searching Algorithms in Python
A search algorithm is a method for finding an item or group of items with specific properties within a collection of items. Here, We will see types of searching algorithms in python. If the value is present in the list, then searching is said to be successful and it displays appropriate message.
However, if the value is not present in the list, the searching process displays an appropriate message and in this case searching is said to be unsuccessful.
There are two popular methods for searching an item from collection of items:
The algorithm that should be used to search any item from the list depends entirely on how the values are organized in the List.
For example, if the items of the array are arranged in ascending order, then binary search should be used, as it is more efficient for sorted lists in terms of complexity.
Here, we will see the algorithms for Linear Search vs Binary Search in Python
Linear Search in Python
Linear Search is a very simple method for searching a list for a particular value. It is also called as sequential search, as it works by comparing the value to be searched sequentially with every element of the list one by one until a match is found.
Linear search is mostly used to search an unordered list of elements (list in which data elements are not sorted). For example, if a list L is initialized as,
L = [10, 8, 2, 7, 3, 4, 9, 1, 6, 5];
Value to be Search is VAL = 7
Value to be search is VAL = 25
Python Program for Linear Search Algorithm
Complexity of Linear Search Algorithm
Linear search executes in O(n) time where n is the number of items in a List.
Obviously, the best case of linear search algorithm is when VAL is equal to the first element of the list. In this case, only one comparison will be made.
Likewise, the worst case will happen when either VAL is not present in the array or it is equal to the last element of the list. In both the cases, n comparisons will have to be made.
Binary Search in Python
Binary search is a searching algorithm that works efficiently with a sorted list.
The mechanism of binary search can be better understood by an analogy of a telephone directory. When we are searching for a particular name in a directory, we first open the directory from the middle and then decide whether to look for the name in the first part of the directory or in the second part of the directory. Again, we open some page in the middle and the whole process is repeated until we finally find the right name.
The same mechanism is applied in the Binary Search Algorithm.
Now, let us consider how this mechanism is applied to search for a value in a sorted list.
Consider a List L of 11 items that is initialized as,
L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
value to be searched is VAL = 9
Value to be search is VAL = 25
The algorithm will proceed in the following manner.
BEG = 0, END = 10, MID = (0 + 10)/2 = 5
Now, VAL = 9 and L[MID] = L = 5
L is less than VAL, therefore, we now search for the value in the second half of the list. So, we change the values of BEG and MID.
Now, BEG = MID + 1 = 6, END = 10, MID = (6 + 10)/2 =16/2 = 8
VAL = 9 and L[MID] = L = 8
L is less than VAL, therefore, we now search for the value in the second half of the segment.
So, again we change the values of BEG and MID.
Now, BEG = MID + 1 = 9, END = 10, MID = (9 + 10)/2 = 9
Now, VAL = 9 and L[MID] = 9.
The algorithm will terminate when L[MID] = VAL. When the algorithm ends, we will set POS = MID. POS is the position at which the value is present in the array.
However, if VAL is not equal to L[MID], then the values of BEG, END, and MID will be changed depending on whether VAL is smaller or greater than L[MID].
(a) If VAL < L[MID], then VAL will be present in the left segment of the list. So, the value of END will be changed as END = MID – 1.
(b) If VAL > L[MID], then VAL will be present in the right segment of the array. So, the value of BEG will be changed as BEG = MID + 1.
Python Program for Binary Search Algorithm
Complexity of Binary Search Algorithm
Binary search executes in O(log n) time where n is the number of items in a List.
Obviously, the best case of binary search algorithm is when VAL is equal to the mid element of the list. In this case, only one comparison will be made.