Module 4: Searching Algorithms

Searching

______ is the process of finding a given value position in a list of values

search key

Searching decides whether a _______ is present in the data or not

algorithmic process

Searching is the _______ of finding a particular item in a collection of items

internal data structure, external data structure

Searching can be done on _______ or on ________

Searching Algorithms

________ are designed to check for an element or retrieve an element from any data structure where it is stored

Sequential Search (Example: Linear Search)

In this, the list or array is traversed sequentially and every element is checked

Interval Search (Example: Binary Search)

These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half.

Linear search

______ is also called as sequential search algorithm. It is the simplest searching algorithm

Linear search

In ________, we simply traverse the list completely and match each element of the list with the item whose location is to be found.

returned, NULL

If the match is found, then the location of the item is _____; otherwise, the algorithm returns _____

O(n)

The worst-case time complexity of linear search is _____

-1

If there is no match or the search element is not present in the given array, return ___

best case, O(1)

In Linear search, ______ occurs when the element we are finding is at the first position of the array. The _______ time complexity of linear search is _____

O(n)

The average case time complexity of linear search is _____

worst case, not present, O(n)

In Linear search, the ______ occurs when the element we are looking is present at the end of the array. The ______ in linear search could be when the target element is _____ in the given array, and we have to traverse the entire array. The worst-case time complexity of linear search is _____

once

The time complexity of linear search is O(n) because every element in the array is compared only ____

O(1)

The space complexity of linear search is ____

Binary search, sorted

_______ is the search technique that works efficiently on _____ lists. Hence, to search an element into some list using the binary search technique, we must ensure that the list is _____.

divide and conquer, two, middle

Binary search follows the ________ approach in which the list is divided into ____ halves, and the item is compared with the _____ element of the list.

middle

In binary search, if the match is found then, the location of the ____ element is returned. Otherwise, we search into either of the halves depending upon the result produced through the match

Iterative method and Recursive method

Two methods to implement the binary search algorithm

recursive method

The _________ of binary search follows the divide and conquer approach

mid = (begin + end)/2

In binary search, the formula to calculate the middle of the array is ______

middle, O(1)

In Binary search, best case occurs when the element to search is found in first comparison, i.e., when the first _____ element itself is the element to be searched. The best-case time complexity of Binary search is ______.

O(log n)

The average case time complexity of Binary search is ______

one, O(log n)

In Binary search, the worst case occurs, when we have to keep reducing the search space till it has only ____ element. The worst-case time complexity of Binary search is ______

O(1)

The space complexity of binary search is ____

Jump Search Algorithm

________ is a relatively new algorithm for searching an element in a sorted array

linear search algorithm

The fundamental idea behind jump search technique is to search fewer number of elements compared to _______ (which scans every element in the array to check if it matches with the element being searched or not)

Interpolation search

_______ is an improved variant of binary search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed

pivot point or probe

Interpolation algorithm is almost similar to that of binary search, except selecting the _______ which is selected based on the value being searched.

linear, O(n), O(log n)

Binary search has a huge advantage of time complexity over _____ search. Linear search has worst-case complexity of ____ whereas binary search has _____

left sub-array

In interpolation search, If the value is smaller, select the______ and repeat steps from starting

right sub-array

In interpolation search, if the value is greater, select the ______ and repeat steps from starting

left sub-array

For descending order in interpolation search, if the value is greater select the _____ and vice versa

mid = Low + (High - Low) * (X - A[Low])
————————————

A[High] - A[Low]

Formula in finding the middle point in interpolation search

Exponential search

_______ is also known as doubling or galloping search. This mechanism is used to find the range where the search key may present.

2

If L and U are the upper and lower bound of the list, then L and U both are the power of ___

binary search

In exponential search, after finding the specific range, it uses the _______ technique to find the exact location of the search key

Fibonacci search algorithm

The ________ is another variant of binary search based on divide and conquer technique

Sublist Search (Search a linked list in another list)

_______ is used to detect a presence of one list in another list.

Jump Search

This can be done by skipping some fixed number of array elements or jumping ahead by fixed number of steps in every iteration