Searching and Sorting
Searching:
I. Linear Search Algorithm:
This method of searching is also called as sequential search
Linear search work on both sorted as well as unsorted list.
Suppose we want to search an element X from the list of N elements. First
the element X is compared with the I element in the List. If the element is
matched then search is successful.
If the element is not matched then the element X is compared with next
element and this process is repeated until match is found or all the elements
in the list are compared.
Algorithm:
step-1 : Start from left most element of list. And one by one compare it with each
element of the list.
step-2: If it matches with the given element, return index
step-3: If it doesn't match with any element, return None.
Example:
The list consist of 5 elements as shown below:
Suppose we want to find 55 in the list. So 55 is compared with the first element in the
list which is 11.
Since match is not found 55 is compared with next element in the list and this
process is repeated until match found or all elements in the list is compared as
shown below.
, Code:
def linear_search(list, x):
for i in range(len(list)):
if list == x:
return i
return None
linear_search([7, 3, 5, 8, 9], 5)
II. Binary Search Algorithm.
Binary search is an efficient algorithm for finding an item from a sorted list of
items.
It is used to reduce the time complexity.
This method of searching is more efficient as compared to linear search
method. Because we does not have to compare the search element with all
the elements in the list until the element is found.
Algorithm:
step-1: Compare x with middle element.
step-2: If x matches with middle element, we return mid index.
step-3: Else if x is greater than mid element, then x can only lie in right half part after
mid element. Then we apply algorithm again for right half part
step-4: Else if x is smaller than mid element, x must lie in left half part, so we apply
algorithm for left half part
Example:
Searching:
I. Linear Search Algorithm:
This method of searching is also called as sequential search
Linear search work on both sorted as well as unsorted list.
Suppose we want to search an element X from the list of N elements. First
the element X is compared with the I element in the List. If the element is
matched then search is successful.
If the element is not matched then the element X is compared with next
element and this process is repeated until match is found or all the elements
in the list are compared.
Algorithm:
step-1 : Start from left most element of list. And one by one compare it with each
element of the list.
step-2: If it matches with the given element, return index
step-3: If it doesn't match with any element, return None.
Example:
The list consist of 5 elements as shown below:
Suppose we want to find 55 in the list. So 55 is compared with the first element in the
list which is 11.
Since match is not found 55 is compared with next element in the list and this
process is repeated until match found or all elements in the list is compared as
shown below.
, Code:
def linear_search(list, x):
for i in range(len(list)):
if list == x:
return i
return None
linear_search([7, 3, 5, 8, 9], 5)
II. Binary Search Algorithm.
Binary search is an efficient algorithm for finding an item from a sorted list of
items.
It is used to reduce the time complexity.
This method of searching is more efficient as compared to linear search
method. Because we does not have to compare the search element with all
the elements in the list until the element is found.
Algorithm:
step-1: Compare x with middle element.
step-2: If x matches with middle element, we return mid index.
step-3: Else if x is greater than mid element, then x can only lie in right half part after
mid element. Then we apply algorithm again for right half part
step-4: Else if x is smaller than mid element, x must lie in left half part, so we apply
algorithm for left half part
Example:
