Search algorithm explanation, binary search algorithm, linear search algorithm, ternary search algorithm

Search algorithm list:

Linear search algorithm:

A linear search, often known as a sequential search, is a method for locating an item in a list. It checks each element of the list one by one until a match is discovered or the entire list is searched.

If each element has an equal chance of being searched, linear search has an average case of (n+1)/2 comparisons, but the average case can be affected if the search probability for each element differ.Because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but the shortest lists, linear search is rarely practical.

we can see it takes 7 steps to search number 4

def linear_search(array_list,element_search):
    
    position = -1
    for i in range(0,len(array_list)):
        if array_list[i] == element_search:
            position += 1
            print("Index of element is : ",i)
            break
        
    if(position == -1):
        print("Element not found")
        
array_list = [3,5,1,2,16,90,4,0]
element_search = 4
linear_search(array_list,element_search)

Binary search algorithm:

The binary search algorithm, also known as the half-interval search algorithm, locates a target value within a sorted array. The target value is compared to the array's middle element in a binary search.If they are not equal, the half where the target cannot lie is eliminated, and the search moves on to the remaining half, comparing the middle element to the target value once more, and repeating until the target value is found. The target is not in the array if the remaining half of the search is empty.
In the worst case, binary search takes logarithmic time, resulting in O(log n) comparisons, where n is the number of elements in the array. Except for small arrays, binary search is faster than linear search.

#Binary Search 
def binary_search(array_list,number_to_search):
left_index = 0
right_index = len(array_list) - 1
mid_index = 0
while left_index <= right_index:
        
    mid_index = (left_index+right_index)//2
    mid_num = array_list[mid_index]
        
    if mid_num == number_to_search:
        return mid_index

    if mid_num < number_to_search:
        left_index = mid_index + 1
    else:
        right_index = mid_index -1
return -1
    
array_list = [0,4,7,10,14,23,45,47,53]
number_to_search = 47
index = binary_search(array_list,number_to_search)
print(f"number found at index {index} using Binary Search")
  

Difference Between Linear and Binary Search 

binary takes only 4 steps while linear takes 8 steps 

Ternary search algorithm:

Ternary search algorithm is used to find the minimum or maximum of a unimodal function. A ternary search determines whether the minimum or maximum cannot be in the first third or last third of the domain, and then repeats the process on the remaining two thirds. A divide and conquer algorithm is an example of a ternary search.

def ternary_search(array_list,number_to_search,left,right):
    if (right >= left):
        mid1 = left + (right - left)//3
        mid2 = mid1 + (right - left)//3
        
        mid1_num = array_list[mid1]
        mid2_num = array_list[mid2]

        if mid1_num == number_to_search:
            return mid1

        if mid2_num == number_to_search:
            return mid2

        if mid1_num > number_to_search:
            return ternary_search(array_list, number_to_search, 1, mid1-1)

        if mid2_num < number_to_search:
            return ternary_search(array_list,number_to_search, mid2+1, right)

        return ternary_search(array_list,number_to_search,mid1+1, mid2-1)

    return -1

array_list = [3,4,10,12,23,34,55,68,73]
number_to_search = 68

result = ternary_search(array_list,number_to_search,1,len(arr_list))
print(f"Index of the element {result}")

.