  ## Searching Algorithms on Python Lists

Searching algorithms are methods to search or traverse data structures to retrieve particular data. Based on the way the data is searched for, searching algorithms can be divided into two types

• Sequential Search - Here each data in the data structure is traversed sequentially till the target element is reached. If not found, all the elements in the data structure are traversed. For example, Linear Search.
• Interval Search - These are specially designed for data structures with elements stored in order ie. sorted. These are much more efficient than Sequential ones. They repeatedly divide the data structure into halves to reduce the area of search. For example, Binary Search.

## Linear Search using Python

Linear Search is a Sequential Search Algorithm that traverses each and every element in the data structure until and unless it reaches the searched data. If it traverses all the data present, then the searched data is not present in the data structure. The time complexity of Linear Search is O(n). The worst-case time complexity is also O(n).

### Linear Search Algorithm

Assumptions: 'array' is an array of 10 elements.

LinearSearch( arguments: array, search_element )

1. Start
2. Input array
3. Input search_element
4. i <- 0
5. While i < = length of array do
1. If search_element = array [ i ] then
1. Return i
2. EndIf
3. i <- i + 1
6. EndWhile
7. Return -1
8. Stop

### Linear Search Code using Python

The Linear Search Algorithm is implemented in Python 3 code as follows.

``````def LinearSearch(array, element):
i = 0
while i < len(array):
if array[i] == element:
return i
i = i + 1
return -1``````

The compiled and implemented program as follows

``````def LinearSearch(array, element):
i = 0
while i < len(array):
if array[i] == element:
return i
i = i + 1
return -1

array1 = [1, 2, 3, 5]
value1 = 3
value2 = 7
if LinearSearch(array1, value1) != -1:
print("The element is found at ", LinearSearch(array1, value1))
else:
print("The element is not present in the array")
if LinearSearch(array1, value2) != -1:
print("The element is found at ", LinearSearch(array1, value2))
else:
print("The element is not present in the array")``````

the output

``````The element is found at  2
The element is not present in the array``````
• Small and medium arrays can be searched quickly
• Easier to understand
• Takes more time to search large datasets and arrays
• All the elements are traversed
• Very slow to process
• Used to search small arrays
• Used to search in Linked Lists

## Binary Search using Python

Binary Search is an Interval Search Algorithm that is applied on ordered or sorted arrays to search for elements. It repeatedly divides the array on the basis of the value to be searched, and the section of the array, that particular value might be present in.

The algorithm calculates the middle index element of that interval and compares it with the value to be searched. If the value is greater than the middle index element, then the starting index for choosing the middle index is updated. Otherwise, if the value is smaller, the ending index is updated.

This process keeps on rolling until the interval is either empty, or the value is found.

Step 1 Step 2 Step 3 Step 4 Step 5 Step 6 The time complexity of Binary Search is O(Log n).

### Binary Search Algorithm

Assumptions: 'array' is an array with numerical data.

BinarySearch( Arguments: array, start, stop, search_element )

1. Start
2. If stop < start then
1. Return -1
3. EndIf
4. mid <- ( start + stop ) / 2
5. If array[ mid ] < search_element then
1. Call BinarySearch( parameters: array, mid + 1, stop, search_element )
6. Else If array[ mid ] > search_element then
1. Call BinarySearch( parameters: array, start, mid - 1, search_element )
7. Else
1. Return mid
8. EndIf
9. Stop

### Binary Search Code using Python

The Python 3 code to implement the Binary Search algorithm is as follows

``````def BinarySearch(array, start, stop, element):
mid = int((start + stop)/2)
if stop < start:
return -1
if array[mid] < element:
return BinarySearch(array, mid + 1, stop, element)
elif array[mid] > element:
return BinarySearch(array, start, mid - 1, element)
else:
return mid``````

The compiled and implemented code is

``````def BinarySearch(array, start, stop, element):
mid = int((start + stop)/2)
if stop < start:
return -1
if array[mid] < element:
return BinarySearch(array, mid + 1, stop, element)
elif array[mid] > element:
return BinarySearch(array, start, mid - 1, element)
else:
return mid

array1 = [1, 2, 3, 5]
value1 = 3
value2 = 7
if BinarySearch(array1, 0, len(array1) - 1, value1) != -1:
print("The element is found at ", BinarySearch(array1, 0, len(array1) - 1, value1))
else:
print("The element is not present in the array")
if BinarySearch(array1, 0, len(array1) - 1, value2) != -1:
print("The element is found at ", BinarySearch(array1, 0, len(array1) - 1, value2))
else:
print("The element is not present in the array")``````

the output of which is

``````The element is found at  2
The element is not present in the array``````