Searching

Search Algorithms

Sl No.	Algorithm	Worst Time	Average Time	Best Time	Memory
1	Linear Search	\[1\]	\[n\]	\[1\]	\[1\]
2	Binary Search	\[log(n)\]	\[log(n)\]	\[1\]	\[1\]

Linear Search

class LinearSearch

Bases: object

linear_search(array, key)

Description

This is a search algorithm that iterates over each element to find the key element

If key is found it will return the position else -1

Important

TIme Complexity

• Worst Case: O(n)

• Average Case: O(n)

• Best Case: O(1)

Space Complexity: O(1)

Python

class LinearSearch:
    def linear_search(self, array, key):
        for i in range(len(array)):
            if array[i] == key:
                return i
        return -1

Implementation

Binary Search

class BinarySearch

Bases: object

binary_search(array, key)

Description

Binary Search is a sorting algorithm, applied on sorted array in which we select the mid element and compare key to the mid element if key is smaller then we search before mid else after mid.

If key is found we return the index of key else -1.

Attention

Finding problems associated with Binary Search

• list/array is sorted

• Have to find element within the sorted list

• Can be used in case of binary values as well eg., [0,0,0,1,1,1,1]

Important

TIme Complexity

• Worst Case: O( log(n) )

• Average Case: O( log(n) )

• Best Case: O(1)

Space Complexity: O(1)

Python

class BinarySearch:
    def binary_search(self, array, key):
        low = 0
        high = len(array) - 1
        while low <= high:
            mid = low + (high - low) // 2
            if array[mid] == key:
                return mid
            elif array[mid] < key:
                low = mid + 1
            else:
                high = mid - 1
        return -1

Implementation

LeetCode

Sl No	Level	Questions	Solutions	Tags
704	Easy	Binary Search	Python
367	Easy	Valid Perfect Square	Python
278	Easy	First Bad Version	Python
74	Medium	Search a 2D Matrix	Python