Searching Algorithms

Searching algorithms are essential tools in computer science used to locate specific items
within a collection of data. These algorithms are designed to efficiently navigate through data
structures to find the desired information, making them fundamental in various applications such
as databases, web search engines, and more.

Table of Content
 What is Searching?
 Searching terminologies
 Importance of Searching in DSA
 Applications of Searching
 Basics of Searching Algorithms
 Searching Algorithms
 Comparisons Between Different Searching Algorithms
 Library Implementations of Searching Algorithms
 Easy Problems on Searching
 Medium Problems on Searching
 Hard Problems on Searching
What is Searching?
Searching is the fundamental process of locating a specific element or item within a collection
of data. This collection of data can take various forms, such as arrays, lists, trees, or other
structured representations. The primary objective of searching is to determine whether the
desired element exists within the data, and if so, to identify its precise location or retrieve it. It
plays an important role in various computational tasks and real-world applications, including
information retrieval, data analysis, decision-making processes, and more.
Searching terminologies:
Target Element:
In searching, there is always a specific target element or item that you want to find within the
data collection. This target could be a value, a record, a key, or any other data entity of interest.
Search Space:
The search space refers to the entire collection of data within which you are looking for the
target element. Depending on the data structure used, the search space may vary in size and
organization.
Complexity:
Searching can have different levels of complexity depending on the data structure and the
algorithm used. The complexity is often measured in terms of time and space requirements.
Deterministic vs. Non-deterministic:
Some searching algorithms, like binary search, are deterministic, meaning they follow a clear,
systematic approach. Others, such as linear search, are non-deterministic, as they may need to
examine the entire search space in the worst case.
Importance of Searching in DSA:
 Efficiency: Efficient searching algorithms improve program performance.
 Data Retrieval: Quickly find and retrieve specific data from large datasets.
 Database Systems: Enables fast querying of databases.
 Problem Solving: Used in a wide range of problem-solving tasks.
Applications of Searching:
 Searching algorithms have numerous applications across various fields. Here are some common
applications:
 Information Retrieval: Search engines like Google, Bing, and Yahoo use sophisticated
searching algorithms to retrieve relevant information from vast amounts of data on the web.
 Database Systems: Searching is fundamental in database systems for retrieving specific data
records based on user queries, improving efficiency in data retrieval.
 E-commerce: Searching is crucial in e-commerce platforms for users to find products
quickly based on their preferences, specifications, or keywords.
 Networking: In networking, searching algorithms are used for routing packets efficiently
through networks, finding optimal paths, and managing network resources.
 Artificial Intelligence: Searching algorithms play a vital role in AI applications, such as
problem-solving, game playing (e.g., chess), and decision-making processes
 Pattern Recognition: Searching algorithms are used in pattern matching tasks, such as
image recognition, speech recognition, and handwriting recognition.
Importance of searching in Data Structure




Searching is a fundamental operation in data structures that involves finding a specific piece
of data within a collection. It is crucial for efficiently retrieving information from a dataset,
especially when dealing with large amounts of data.
Importance of Searching in Data Structures:
Searching is a fundamental operation in data structures. It allows us to find specific data items
within a collection of data. Efficient searching is crucial for many applications, including:
 Databases: Searching for records based on criteria
 Search engines: Finding web pages relevant to a query
 Artificial intelligence: Identifying patterns and making decisions
 Data analysis: Extracting insights from large datasets
Types of Searching:
There are two main types of searching:
 Linear search: Iterates through the entire collection, comparing each element to the target
value.
 Binary search: Divides the collection into smaller and smaller halves, narrowing down the
search range.
Factors Affecting Search Efficiency:
The efficiency of a search operation depends on several factors:
 Size of the collection: Larger collections take more time to search.
 Type of data structure: Some data structures (e.g., arrays) are more efficient for searching
than others (e.g., linked lists).
 Search algorithm: Different search algorithms have varying time complexities.
Importance of Data Structures for Searching:
Arrays:
 Allow for fast linear search, where each element is checked sequentially.
 Efficient for binary search, which divides the array into halves until the target element is
found.
Linked Lists:
 Useful for inserting and deleting elements efficiently.
 Slower for searching as each node must be traversed sequentially.
Hash Tables:
 Provide constant-time search by storing data in a key-value pair format.
 The key is used to compute the location of the data in the table.
Trees:
 Organize data hierarchically, enabling efficient binary search.
 Support range queries, where all elements within a specified range can be retrieved
efficiently.
Specific Examples:
 Linear Search: Arrays are ideal for linear search due to their contiguous memory layout.
 Binary Search: Binary search is most efficient with sorted arrays, as it can divide the array
into halves to quickly narrow down the search space.
 Hashing: Hash tables are used in scenarios where fast and efficient lookups are required,
such as in databases or in-memory caches.
 Binary Search Tree (BST): BSTs allow for efficient binary search and range queries. The
data is organized in a hierarchical structure, where each node contains a key and a value.
Conclusion:
Searching is an essential operation in data structures that enables us to find specific data items
efficiently. The type of search algorithm and data structure used play a crucial role in
determining the search performance. Understanding the importance of searching and the
factors that affect its efficiency is essential for designing and implementing effective data
structures and algorithms.

Searching Algorithms:
Linear Search
Sentinel Linear Search
Binary Search
Meta Binary Search | One-Sided Binary Search
Ternary Search
Jump Search
Interpolation Search
Exponential Search
Fibonacci Search
The Ubiquitous Binary Search

Introduction to Linear Search Algorithm

Linear Search Algorithm
The linear search algorithm is defined as a sequential search
algorithm that starts at one end and goes through each element of a
list until the desired element is found; otherwise, the search
continues till the end of the dataset. In this article, we will learn
about the basics of the linear search algorithm, its applications,
advantages, disadvantages, and more to provide a deep
understanding of linear search.
Table of Content
 What is Linear Search Algorithm?
 Algorithm for Linear Search Algorithm
 How Does Linear Search Algorithm Work?
 Implementation of Linear Search Algorithm
 Time and Space Complexity of Linear Search Algorithm
 Applications of Linear Search Algorithm
 Advantages of Linear Search Algorithm
 Disadvantages of Linear Search Algorithm
 When to use Linear Search Algorithm?
 Frequently Asked Questions (FAQs) on Linear Search Algorithm
What is Linear Search Algorithm?
Linear search is a method for searching for an element in a collection of elements. In linear
search, each element of the collection is visited one by one in a sequential fashion to find the
desired element. Linear search is also known as sequential search.
Algorithm for Linear Search Algorithm:
The algorithm for linear search can be broken down into the following steps:
 Start: Begin at the first element of the collection of elements.
 Compare: Compare the current element with the desired element.
 Found: If the current element is equal to the desired element, return true or index to the
current element.
 Move: Otherwise, move to the next element in the collection.
 Repeat: Repeat steps 2-4 until we have reached the end of collection.
 Not found: If the end of the collection is reached without finding the desired element, return
that the desired element is not in the array.
How Does Linear Search Algorithm Work?
In Linear Search Algorithm,
 Every element is considered as a potential match for the key and checked for the same.
 If any element is found equal to the key, the search is successful and the index of that
element is returned.
 If no element is found equal to the key, the search yields “No match found”.
For example:
Consider the array arr[] = {10, 50, 30, 70, 80, 20, 90, 40} and key = 30
Step 1:
Start from the first element (index 0) and compare key with each
element (arr[i]).
 Comparing key with first element arr[0]. SInce not equal, the
iterator moves to the next element as a potential match.
 Compare key with arr[0]

Comparing key with next element arr[1].

Since not equal, the iterator moves to the next element as a potential match.

 Step 2: Now when comparing arr[2] with key, the value matches. So
the Linear Search Algorithm will yield a successful message and
return the index of the element when key is found (here 2).
 Compare key with arr[2]
Implementation of Linear Search Algorithm:
In Linear Search, we iterate over all the elements of the array and check if it the current element
is equal to the target element. If we find any element to be equal to the target element, then
return the index of the current element. Otherwise, if no element is equal to the target element,
then return -1 as the element is not found.
Below is the implementation of the linear search algorithm:

# Python code to linearly search x in arr[].

def search(arr, N, x):

for i in range(0, N):

if (arr[i] == x):
return i
return -1

# Driver Code
if __name__ == "__main__":
arr = [2, 3, 4, 10, 40]
x = 10
N = len(arr)

# Function call
result = search(arr, N, x)
if(result == -1):
print("Element is not present in array")
else:
print("Element is present at index", result)

Output
Element is present at index 3

Time Complexity:
 Best Case: In the best case, the key might be present at the first index. So the best case
complexity is O(1)
 Worst Case: In the worst case, the key might be present at the last index i.e., opposite to the
end from which the search has started in the list. So the worst-case complexity is O(N) where
N is the size of the list.
 Average Case: O(N)
Auxiliary Space: O(1) as except for the variable to iterate through the list, no other variable is
used.
Applications of Linear Search Algorithm:
 Unsorted Lists: When we have an unsorted array or list, linear search is most commonly
used to find any element in the collection.
 Small Data Sets: Linear Search is preferred over binary search when we have small data sets
with
 Searching Linked Lists: In linked list implementations, linear search is commonly used to
find elements within the list. Each node is checked sequentially until the desired element is
found.
 Simple Implementation: Linear Search is much easier to understand and implement as
compared to Binary Search or Ternary Search.
Advantages of Linear Search Algorithm:
 Linear search can be used irrespective of whether the array is sorted or not. It can be used on
arrays of any data type.
 Does not require any additional memory.
 It is a well-suited algorithm for small datasets.
Disadvantages of Linear Search Algorithm:
 Linear search has a time complexity of O(N), which in turn makes it slow for large datasets.
 Not suitable for large arrays.
When to use Linear Search Algorithm?
 When we are dealing with a small dataset.
 When you are searching for a dataset stored in contiguous memory.
Frequently Asked Questions (FAQs) on Linear Search Algorithm:
1. What is linear search algorithm?
Linear search algorithm, also known as sequential search algorithm, is a simple searching
algorithm that traverses a list or array sequentially to find a target element. In Linear Search,
we can get the
2. How does linear search algorithm work?
Linear search algorithm iterates through each element in the list or array, comparing it with the
target element until a match is found or the end of the list is reached. If the end of the list is
reached, then it means that the target element is not present in the array.
3. What is the time complexity of linear search algorithm?
The time complexity of linear search algorithm is O(n), where n is the number of elements in the
list or array being searched. This means the time taken for searching increases linearly with the
size of the input.
4. When is linear search algorithm preferred over other searching algorithms?
Linear search algorithm is preferred when the list or array is unsorted, or when the size of the
input is relatively small. It’s simple to implement and doesn’t require the data to be in any
specific order.
5. What are the advantages of linear search algorithm?
Linear search algorithm is easy to implement, and it works efficiently on small-sized arrays or
lists. It doesn’t require any pre-processing like sorting, making it suitable for dynamic data
structures.
6. What are the disadvantages of linear search algorithm?
Linear search algorithm becomes inefficient for large-sized arrays or lists, as it needs to scan
through each element sequentially. It has a time complexity of O(n), which means the search
time grows linearly with the size of the input.
7. How do you implement linear search algorithm in programming languages like Python,
Java, or C++?
Linear search algorithm can be implemented using loops to iterate through the elements of the
array or list, comparing each element with the target value until a match is found or the end of
the list is reached.
8. Can linear search algorithm be applied to other data structures?
Yes, linear search algorithm can be applied not only to arrays or lists but also to other linear
data structures like linked lists. The principle remains the same: iterating through each element
until the target is found or the end is reached.
9. Is linear search algorithm suitable for sorted arrays or lists?
While linear search algorithm can still be used on sorted arrays or lists, it’s not the most
efficient option. Binary search, for example, is more suitable for sorted data as it has a time
complexity of O(log n).
10. What are some real-world applications of linear search algorithm?
Linear search algorithm can be used in scenarios such as searching for a specific value in a
phone book, searching for a name in an unsorted list of contacts, or finding an item in a grocery
list. It’s often used in scenarios where the data size is small or not expected to grow
significantly.

Sentinel Linear Search

 Sentinel Linear Search as the name suggests is a type of Linear Search where the number of
comparisons is reduced as compared to a traditional linear search. In a traditional linear
search, only N comparisons are made, and in a Sentinel Linear Search, the sentinel value is
used to avoid any out-of-bounds comparisons, but there is no additional comparison made
specifically for the index of the element being searched.
In this search, the last element of the array is replaced with the element to be searched and
then the linear search is performed on the array without checking whether the current index is
inside the index range of the array or not. Because the element to be searched will definitely
be found inside the array even if it was not present in the original array since the last element
got replaced with it. So, the index to be checked will never be out of the bounds of the array.
The number of comparisons in the worst case there will be (N + 2).
 Sentinel linear search is a variation of the standard linear search algorithm used to find a
target value in an array or list. The basic idea behind this algorithm is to add a sentinel value
at the end of the array which is equal to the target value we are looking for. This helps to
avoid checking the array boundary condition during each iteration of the loop, as the sentinel
value acts as a stopper for the loop.
 Although in worst-case time complexity both algorithms are O(n). Only the number of
comparisons are less in sentinel linear search than linear search
Use of the Sentinel Linear Search :
 In the context of searching for an element in an array, Sentinel Linear Search is a variant of
Linear Search algorithm that uses a sentinel value to optimize the search process.
 The basic idea of Sentinel Linear Search is to add an extra element at the end of the array
(i.e., the sentinel value) that matches the search key. By doing so, we can avoid the
conditional check for the end of the array in the loop and terminate the search early, as soon
as we find the sentinel element. This eliminates the need for a separate check for the end of
the array, resulting in a slight improvement in the average case performance of the algorithm.
 Here are the steps for Sentinel Linear Search algorithm:
 Initialize the search index variable i to 0.
 Set the last element of the array to the search key.
 While the search key is not equal to the current element of the array (i.e., arr[i]), increment
the search index i.
 If i is less than the size of the array or arr[i] is equal to the search key, return the value of i
(i.e., the index of the search key in the array).
 Otherwise, the search key is not present in the array, so return -1 (or any other appropriate
value to indicate that the key is not found).
 The key benefit of the Sentinel Linear Search algorithm is that it eliminates the need for a
separate check for the end of the array, which can improve the average case performance of
the algorithm. However, it does not improve the worst-case performance, which is still O(n)
(where n is the size of the array), as we may need to scan the entire array to find the sentinel
value.
Examples:
Input: arr[] = {10, 20, 180, 30, 60, 50, 110, 100, 70}, x = 180
Output: 180 is present at index 2
Input: arr[] = {10, 20, 180, 30, 60, 50, 110, 100, 70}, x = 90
Output: Not found
Below is the implementation of the above approach:
# Python3 implementation of the approach
# Function to search key in the given array

def sentinelSearch(arr, n, key):

# Last element of the array

last = arr[n - 1]

# Element to be searched is
# placed at the last index
arr[n - 1] = key
i = 0

while (arr[i] != key):

i += 1

# Put the last element back

arr[n - 1] = last

if ((i < n - 1) or (arr[n - 1] == key)):

 print(key, "is present at index", i)
else:
print("Element Not found")

# Driver code
arr = [10, 20, 180, 30, 60, 50, 110, 100, 70]
n = len(arr)
key = 180

sentinelSearch(arr, n, key)

Output
180 is present at index 2
Time Complexity: O(N)
Auxiliary Space: O(1)
Method 2 :

Here are the steps involved in the Sentinel Linear Search

Algorithm:

1. Set the last element of the array to the target value. This is
known as the sentinel value.
2. Set the index variable “i” to the first element of the array.
3. Use a loop to iterate through the array, comparing each element
with the target value.
4. If the current element is equal to the target value, return the
index of the current element.
5. Increment the index variable “i” by 1 after each iteration of the
loop.
6. If the loop completes and the target value is not found, return -1
to indicate that the value is not present in the array.
The sentinel linear search algorithm is useful for arrays with a large
number of elements where the target value may be located towards
the end of the array. By adding the sentinel value at the end of the
array, we can eliminate the need to check the array boundary
condition during each iteration of the loop, thereby reducing the
overall running time of the algorithm.

Python
def sentinelLinearSearch(array, key):
last = array[len(array) - 1]
array[len(array) - 1] = key
i =0
while array[i] != key:
i += 1
array[len(array) - 1] = last
 if i < len(array) - 1 or last == key:
return i
else:
return -1

array = [1, 2, 3, 4, 5, 6, 7, 8, 9]
key = 5
index = sentinelLinearSearch(array, key)
if index == -1:
print(f"{key} is not found in the array: {array}")
else:
print(f"{key} is found at index {index} in the array: {array}")

Output
5 is found at index 4 in the array: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Time Complexity :

The time complexity of the Sentinel Linear Search algorithm is O(n)

in the worst case.
In the best case, when the key is found in the first iteration, the time
complexity will be O(1).
However, the average time complexity is still O(n), because on
average, the key will be found after

Binary Search Algorithm – Iterative and Recursive Implementation

Binary Search Algorithm is a searching algorithm used in a sorted array by repeatedly

dividing the search interval in half. The idea of binary search is to use the information that
the array is sorted and reduce the time complexity to O(log N).

Binary Search Algorithm

Table of Content
 What is Binary Search Algorithm?
 Conditions to apply Binary Search Algorithm in a Data Structure
 Binary Search Algorithm
 How does Binary Search Algorithm work?
 How to Implement Binary Search Algorithm?
o Iterative Binary Search Algorithm:
o Recursive Binary Search Algorithm:
 Complexity Analysis of Binary Search Algorithm
 Applications of Binary Search Algorithm
 Advantages of Binary Search
 Disadvantages of Binary Search
 Frequently Asked Questions(FAQs) on Binary Search

What is Binary Search Algorithm?

Binary search is a search algorithm used to find the position of a target value within
a sorted array. It works by repeatedly dividing the search interval in half until the target value is
found or the interval is empty. The search interval is halved by comparing the target element
with the middle value of the search space.
Conditions to apply Binary Search Algorithm in a Data Structure
To apply Binary Search algorithm:
 The data structure must be sorted.
 Access to any element of the data structure should take constant time.
Binary Search Algorithm
Below is the step-by-step algorithm for Binary Search:
 Divide the search space into two halves by finding the middle index “mid”.
 Compare the middle element of the search space with the key.
 If the key is found at middle element, the process is terminated.
 If the key is not found at middle element, choose which half will be used as the next search
space.
o If the key is smaller than the middle element, then the left side is used for next
search.
o If the key is larger than the middle element, then the right side is used for next
search.
 This process is continued until the key is found or the total search space is exhausted.
Binary Search Visualizer

How does Binary Search Algorithm work?

To understand the working of binary search, consider the following illustration:
Consider an array arr[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91}, and the target = 23.
How to Implement Binary Search Algorithm?
The Binary Search Algorithm can be implemented in the following two ways
 Iterative Binary Search Algorithm
 Recursive Binary Search Algorithm
Given below are the pseudocodes for the approaches.
Iterative Binary Search Algorithm:
Here we use a while loop to continue the process of comparing the key and splitting the search
space in two halves.

Binary Search
# Python3 code to implement iterative Binary
# Search.

# It returns location of x in given array arr

def binarySearch(arr, low, high, x):

while low <= high:

mid = low + (high - low) // 2

# Check if x is present at mid

if arr[mid] == x:
return mid

# If x is greater, ignore left half

elif arr[mid] < x:
low = mid + 1

# If x is smaller, ignore right half

else:
high = mid - 1

# If we reach here, then the element

# was not present
return -1
# Driver Code
if __name__ == '__main__':
arr = [2, 3, 4, 10, 40]
x = 10

# Function call
result = binarySearch(arr, 0, len(arr)-1, x)
if result != -1:
print("Element is present at index", result)
else:
print("Element is not present in array")

Output
Element is present at index 3
Time Complexity: O(log N)
Auxiliary Space: O(1)
Recursive Binary Search Algorithm:
Create a recursive function and compare the mid of the search space with the key. And based on
the result either return the index where the key is found or call the recursive function for the next
search space.
Python
# Python3 Program for recursive binary search.
# Returns index of x in arr if present, else -1
def binarySearch(arr, low, high, x):

# Check base case

if high >= low:

mid = low + (high - low) // 2

# If element is present at the middle itself

if arr[mid] == x:
return mid

# If element is smaller than mid, then it

# can only be present in left subarray
elif arr[mid] > x:
return binarySearch(arr, low, mid-1, x)

# Else the element can only be present

# in right subarray
else:
return binarySearch(arr, mid + 1, high, x)

# Element is not present in the array

else:
 return -1

# Driver Code
if __name__ == '__main__':
arr = [2, 3, 4, 10, 40]
x = 10

# Function call
result = binarySearch(arr, 0, len(arr)-1, x)

if result != -1:
print("Element is present at index", result)
else:
print("Element is not present in array")

Output
Element is present at index 3
 Time Complexity:
o Best Case: O(1)
o Average Case: O(log N)
o Worst Case: O(log N)
 Auxiliary Space: O(1), If the recursive call stack is considered then the auxiliary space will be
O(logN).
Applications of Binary Search Algorithm
 Binary search can be used as a building block for more complex algorithms used in machine
learning, such as algorithms for training neural networks or finding the optimal
hyperparameters for a model.
 It can be used for searching in computer graphics such as algorithms for ray tracing or texture
mapping.
 It can be used for searching a database.
Advantages of Binary Search
 Binary search is faster than linear search, especially for large arrays.
 More efficient than other searching algorithms with a similar time complexity, such as
interpolation search or exponential search.
 Binary search is well-suited for searching large datasets that are stored in external memory,
such as on a hard drive or in the cloud.
Disadvantages of Binary Search
 The array should be sorted.
 Binary search requires that the data structure being searched be stored in contiguous memory
locations.
 Binary search requires that the elements of the array be comparable, meaning that they must
be able to be ordered.
Frequently Asked Questions(FAQs) on Binary Search
1. What is Binary Search?
Binary search is an efficient algorithm for finding a target value within a sorted array. It works
by repeatedly dividing the search interval in half.
2. How does Binary Search work?
Binary Search compares the target value to the middle element of the array. If they are equal,
the search is successful. If the target is less than the middle element, the search continues in the
lower half of the array. If the target is greater, the search continues in the upper half. This
process repeats until the target is found or the search interval is empty.
3. What is the time complexity of Binary Search?
The time complexity of binary search is O(log2n), where n is the number of elements in the
array. This is because the size of the search interval is halved in each step.
4. What are the prerequisites for Binary Search?
Binary search requires that the array is sorted in ascending or descending order. If the array is
not sorted, we cannot use Binary Search to search an element in the array.
5. What happens if the array is not sorted for binary search?
If the array is not sorted, binary search may return incorrect results. It relies on the sorted
nature of the array to make decisions about which half of the array to search.
6. Can binary search be applied to non-numeric data?
Yes, binary search can be applied to non-numeric data as long as there is a defined order for the
elements. For example, it can be used to search for strings in alphabetical order.
7. What are some common disadvantages of Binary Search?
The disadvantage of Binary Search is that the input array needs to be sorted to decide which in
which half the target element can lie. Therefore for unsorted arrays, we need to sort the array
before applying Binary Search.
8. When should Binary Search be used?
Binary search should be used when searching for a target value in a sorted array, especially
when the size of the array is large. It is particularly efficient for large datasets compared to
linear search algorithms.
9. Can binary search be implemented recursively?
Yes, binary search can be implemented both iteratively and recursively. The recursive
implementation often leads to more concise code but may have slightly higher overhead due to
recursive stack space or function calls.
10. Is Binary Search always the best choice for searching in a sorted array?
While binary search is very efficient for searching in sorted arrays, there may be specific cases
where other search algorithms are more appropriate, such as when dealing with small datasets
or when the array is frequently modified.
Linear Search vs Binary Search

Prerequisite:
 Linear Search
 Binary Search
LINEAR SEARCH
Assume that item is in an array in random order and we have to find an item. Then the only way
to search for a target item is, to begin with, the first position and compare it to the target. If the
item is at the same, we will return the position of the current item. Otherwise, we will move to
 the next position. If we arrive at the last position of an array and still can not find the target, we
return -1. This is called the Linear search or Sequential search.

Below is the code syntax for the linear search.

Python
# Linear Search in Python

def linearSearch(array, n, x):

for i in range(0, n):

if (array[i] == x):
return i
return -1

BINARY SEARCH
In a binary search, however, cut down your search to half as soon as you find the middle of a
sorted list. The middle element is looked at to check if it is greater than or less than the value to
be searched. Accordingly, a search is done to either half of the given list

Python
def binarySearch(array, x, low, high):

# Repeat until the pointers low and high meet each other
while low <= high:

mid = low + (high - low)//2

if array[mid] == x:
return mid

elif array[mid] < x:

low = mid + 1

else:
high = mid - 1

return -1
Important Differences
Linear Search Binary Search

In linear search input data need not to be in In binary search input data need to be in
sorted. sorted order.
 Linear Search Binary Search

It is also called sequential search. It is also called half-interval search.

The time complexity of binary search O(log

The time complexity of linear search O(n).
n).

Multidimensional array can be used. Only single dimensional array is used.

Binary search performs ordering

Linear search performs equality comparisons
comparisons

It is less complex. It is more complex.

It is very slow process. It is very fast process.

Let us look at an example to compare the two:

Linear Search to find the element “J” in a given sorted list from A-X

Binary Search to find the element “J” in a given sorted list from A-X

LINEAR SEARCHING EXAMPLE:

Python
def linearSearch(array, n, x):

for i in range(0, n):

if (array[i] == x):
return i
return -1
array = [24, 41, 31, 11, 9]
x = 11
n = len(array)
result = linearSearch(array, n, x)
if(result == -1):
print("Element not found")
else:
print("Element is Present at Index: ", result)
Output
Element found at index: 3
Time Complexity: O(n), where n is the size of the input array. The worst-case scenario is when
the target element is not present in the array, and the function has to go through the entire array
to figure that out.
Auxiliary Space: O(1), the function uses only a constant amount of extra space to store
variables. The amount of extra space used does not depend on the size of the input array.

BINARY SEARCHING EXAMPLE:

Python
def binarySearch(array, x, low, high):

while low <= high:

mid = low + (high - low)//2

if array[mid] == x:
return mid

elif array[mid] < x:

low = mid + 1

else:
high = mid - 1

return -1

array = [2, 4, 5, 7, 14, 17, 19, 22]

x = 22

result = binarySearch(array, x, 0, len(array)-1)

if result != -1:
print(str(result))
else:
print("Not found")

Output
7
How to Identify & Solve Binary Search Problems?
We all know that Binary search is the most efficient search algorithm as of now, and it has
multiple applications in the programming domain for the same reason. But very often the
problems do not have any information about applying Binary Search or even any hint on using
a Searching algorithm altogether. So it becomes very important to have an understanding
of how to identify Binary Search Problems, how to solve Binary Search problems and
what are the most common interview questions that have a Binary Search solution
involved. In this post, we have curated the topics to do just that.
Table of Content
 What is the Binary Search Technique?
 Possible Cases of problems and in which Case binary search can be applied or not:
 How to Identify Binary Search Problems?
 How to Solve Binary Search Problems?
 Example to show How to Identify & Solve a Problem using Binary search:
 Most Common Interview Problems on Binary Search

What is the Binary Search Technique?

Binary search is a searching technique to search an ordered list of data based on the Divide
and Conquer technique which repeatedly divides the search space by half in every iteration.
Possible types of problems and in which type Binary Search can be applied or not:
1) When Input is sorted:
In this case, Identification as a binary search problem is very straightforward as we can easily
deduce which half needs to be removed from the search space.
2)When Input is unsorted but the problem follows a monotonic nature:
In this case also binary search can be applied as the problem follows a monotonic nature which
means the function can be either increasing or decreasing with an increase in a parameter so
that one-half can be removed from search space.
3)When the Expected answer is ordered:
Whenever we can identify that the answer to the problem lies between in a range L to R and
there is a Monotonic Behaviour of the answer in range L to R then we can think to apply
binary search on the answer.
4)When Neither input is sorted nor the problem follows monotonic behavior:

In this case we can not apply binary search.

 Identify and Solve Binary Search Problems

Now here is the general technique to Identify and Solve the Binary search problems.
How to Identify Binary Search Problems?
Based on the number of problems involving Binary Search, we can safely assume the scenario
when Binary search is involved in a problem, as mentioned below:
Binary search can only be applied to a problem if and only if the Problem is monotonic in
nature.
Binary Searchable elements
When a Problem is considered to be Monotonic?
Suppose we are given a problem f() and the expected solution to this problem is y, then we can
define the problem as
y = f(n)
Now if this problem show a behaviour such that it either only increases or only decreases with
the change in parameter. Then it is said that the problem shows Monotonic (only single
direction) behaviour.
In other words, A function f(n1) is said to be monotonic if and only if:
 for any n1, if f(n1) returns true, then for any value of n2 (where n2 > n1), f(n2) should
also return true,
 and similarly, if for a certain value of n1 for which f(n1) is false, then for any
value n2 (n2 < n1) the function f(n2) should also return false.
The same is shown in the graph below:

Monotonic Functions

Now if this problem shows a monotonic behavior, generally this tells you that you can apply a
binary search here.
How to Solve Binary Search Problems?
 Define a search space by pointers let’s say low to high.
 Calculate mid value of search space,and check mid value is true or false.
 Considering above resut figure out where expected answer should lie, In the left half or
right half Then update the search space accordingly.
 Repeat the above steps till there is search space left to search.

Example to show How to Identify & Solve a Problem using Binary search:

Problem Statement : Given an array arr[] of integers and a number x, the task is to find the
minimum length of subarray with a sum greater than the given value k.
Example:
Input: arr[] = {1, 4, 45, 6, 0, 19}, x = 51
Output: 3
Explanation:Minimum length subarray is {4, 45, 6}
Identification as a Binary Search Problem:
Let n1 is size of subarray and f(n1) is true i.e. there is a subarray of size n1 whose sum is
greater than x.
Take any n2 (n2>n1) i.e at least one more element than previous subarray size then it is
guaranteed that f(n2) must hold true because there is subarray of size n1 has sum greater
than x, adding at least one non-negative integer increases the sum.
Problem is monotonic in nature and can be solved using binary search.
Solution of the Problem using Binary search:
 Define search space
o low = 0,as minimum size of subarray can be zero.
o high = length of the array, as subarray size can be up to length of array.
 Calculate mid value as (low+high)/2 and check f(mid) returns true or false.
o Check sum of every subarray of size mid is greater than x or not using sliding
window.
o if there is a subarray present then f(mid) is true.
o else f(mid) is false.
 Update the search space:
o if f(mid) is true and minimal length to be find then expected answer should lie
in left half (high = mid-1) as in the right half of mid all the value are true, store
the mid value as best possible answer till now.
o if f(mid) is false i.e. there is no subarray of size mid,so size need to be increased
to increase the sum.Means expected answer should lie in the right half(low
=mid+1).
 Repeat the above steps with updated search space till there is search space to search.
Implementation of the above solution:

Python
def f(mid, arr, n, x):
# Initialize variables
is_subarray = False
i, j, summation = 0, 0, 0

# Calculate initial sum of the subarray of size 'mid'

for j in range(mid):
 summation += arr[j]

# Sliding window approach to find subarrays whose sum exceeds 'x'

while j < n:
if summation > x:
is_subarray = True # Set flag if sum exceeds 'x'
summation -= arr[i] # Update sum by removing arr[i]
summation += arr[j] # Update sum by adding arr[j]
i += 1 # Move window start pointer
j += 1 # Move window end pointer

if summation > x:
is_subarray = True # Check the last subarray before
exiting

return is_subarray

def smallestSubWithSum(arr, n, x):

low, high, ans = 0, n, float('inf')

# Binary search to find the smallest subarray whose sum is less

than 'x'
while low <= high:
mid = (low + high) // 2

# Check if there exists a subarray of size 'mid' whose sum

exceeds 'x'
if f(mid, arr, n, x):
ans = mid # Update answer to current mid
high = mid - 1 # Reduce search space to the left
else:
low = mid + 1 # Move to the right in the search space

return ans if ans != float('inf') else 0 # Return the smallest

subarray size or 0 if not found

# Driver code
arr = [1, 4, 45, 6, 0, 19]
n = 6
x = 51
print(smallestSubWithSum(arr, n, x)) # Output the result of smallest
subarray sum less than 'x'

Output
3

Time Complexity:O(NlogN),N is the size of the subarray

Auxiliary space: O(1)

Meta Binary Search | One-Sided Binary Search

Meta binary search (also called one-sided binary search by Steven Skiena in The Algorithm
Design Manual on page 134) is a modified form of binary search that incrementally constructs
the index of the target value in the array. Like normal binary search, meta binary search takes
O(log n) time.
Meta Binary Search, also known as One-Sided Binary Search, is a variation of the binary search
algorithm that is used to search an ordered list or array of elements. This algorithm is designed to
reduce the number of comparisons needed to search the list for a given element.
The basic idea behind Meta Binary Search is to start with an initial interval of size n that includes
the entire array. The algorithm then computes a middle element, as in binary search, and
compares it to the target element. If the target element is found, the search terminates. If the
middle element is greater than the target element, the algorithm sets the new interval to the left
half of the previous interval, and if the middle element is less than the target element, the new
interval is set to the right half of the previous interval. However, unlike binary search, Meta
Binary Search does not perform a comparison for each iteration of the loop.
Instead, the algorithm uses a heuristic to determine the size of the next interval. It computes the
difference between the value of the middle element and the value of the target element, and
divides the difference by a predetermined constant, usually 2. This result is then used as the size
of the new interval. The algorithm continues until it finds the target element or determines that it
is not in the list.
The advantage of Meta Binary Search over binary search is that it can perform fewer
comparisons in some cases, particularly when the target element is close to the beginning of the
list. The disadvantage is that the algorithm may perform more comparisons than binary search in
other cases, particularly when the target element is close to the end of the list. Therefore, Meta
Binary Search is most effective when the list is ordered in a way that is consistent with the
distribution of the target elements.

Here is the pseudocode for Meta Binary Search:

function meta_binary_search(A, target):
n = length(A)
interval_size = n
while interval_size > 0:
index = min(n - 1, interval_size / 2)
mid = A[index]
if mid == target:
return index
elif mid < target:
interval_size = (n - index) / 2
else:
interval_size = index / 2
 return -1

Examples:
Input: [-10, -5, 4, 6, 8, 10, 11], key_to_search = 10
Output: 5

Input: [-2, 10, 100, 250, 32315], key_to_search = -2

Output: 0
The exact implementation varies, but the basic algorithm has two parts:
1. Figure out how many bits are necessary to store the largest array index.
2. Incrementally construct the index of the target value in the array by determining whether
each bit in the index should be set to 1 or 0.
Approach:
1. Store number of bits to represent the largest array index in variable lg.
2. Use lg to start off the search in a for loop.
3. If the element is found return pos.
4. Otherwise, incrementally construct an index to reach the target value in the for loop.
5. If element found return pos otherwise -1.
Below is the implementation of the above approach:

# Python 3 implementation of
# above approach

# Function to show the working

# of Meta binary search
import math
def bsearch(A, key_to_search):

n = len(A)
# Set number of bits to represent
lg = int(math.log2(n-1)) + 1;

# largest array index

#while ((1 << lg) < n - 1):
#lg += 1

pos = 0
for i in range(lg - 1, -1, -1) :
if (A[pos] == key_to_search):
return pos

# Incrementally construct the

# index of the target value
new_pos = pos | (1 << i)

# find the element in one

# direction and update position
 if ((new_pos < n) and
(A[new_pos] <= key_to_search)):
pos = new_pos

# if element found return

# pos otherwise -1
return (pos if(A[pos] == key_to_search) else -1)

# Driver code
if __name__ == "__main__":

A = [ -2, 10, 100, 250, 32315 ]

print( bsearch(A, 10))

Ternary Search
Computer systems use different methods to find specific data. There are various search
algorithms, each better suited for certain situations. For instance, a binary search divides
information into two parts, while a ternary search does the same but into three equal parts.
It’s worth noting that ternary search is only effective for sorted data. In this article, we’re going
to uncover the secrets of Ternary Search – how it works, why it’s faster in some situations.

Table of Content
 What is the Ternary Search?
 When to use Ternary Search
 Working of Ternary Search
 Implementation of Ternary Search
 Complexity Analysis of Ternary Search
 Binary search Vs Ternary Search
 Advantages
 Disadvantages
 Summary
What is the Ternary Search?
Ternary search is a search algorithm that is used to find the position of a target value within a
sorted array. It operates on the principle of dividing the array into three parts instead of two, as
in binary search. The basic idea is to narrow down the search space by comparing the target
value with elements at two points that divide the array into three equal parts.
 mid1 = l + (r-l)/3
 mid2 = r – (r-l)/3
When to use Ternary Search:
 When you have a large ordered array or list and need to find the position of a specific value.
 When you need to find the maximum or minimum value of a function.
 When you need to find bitonic point in a bitonic sequence.
 When you have to evaluate a quadratic expression
Working of Ternary Search:
The concept involves dividing the array into three equal segments and determining in which
segment the key element is located. It works similarly to a binary search, with the distinction of
reducing time complexity by dividing the array into three parts instead of two.
Below are the step-by-step explanation of working of Ternary Search:
1. Initialization:
 Set two pointers, left and right, initially pointing to the first and last elements of our
search space.
2. Divide the search space:
 Calculate two midpoints, mid1 and mid2, dividing the current search space into three
roughly equal parts:
 mid1 = left + (right – left) / 3
 mid2 = right – (right – left) / 3
 The array is now effectively divided into [left, mid1], (mid1, mid2), and [mid2, right].
3. Comparison with Target:.
 If the target is equal to the element at mid1 or mid2, the search is successful, and the
index is returned
 If the target is less than the element at mid1, update the right pointer to mid1 – 1.
 If the target is greater than the element at mid2, update the left pointer to mid2 + 1.
 If the target is between the elements at mid1 and mid2, update the left pointer to mid1 +
1 and the right pointer to mid2 – 1.
4. Repeat or Conclude:
 Repeat the process with the reduced search space until the target is found or the search
space becomes empty.
 If the search space is empty and the target is not found, return a value indicating that
the target is not present in the array.

Illustration:
Implementation:
Below is the implementation of Ternary Search Approach:
Recommended Problem
Searching an element in a sorted array (Ternary Search)

# Python3 program to illustrate

# recursive approach to ternary search
import math as mt

# Function to perform Ternary Search

def ternarySearch(l, r, key, ar):

if (r >= l):

# Find the mid1 and mid2

mid1 = l + (r - l) //3
mid2 = r - (r - l) //3

# Check if key is present at any mid

if (ar[mid1] == key):
return mid1

if (ar[mid2] == key):
return mid2

# Since key is not present at mid,

# check in which region it is present
# then repeat the Search operation
# in that region
if (key < ar[mid1]):

# The key lies in between l and mid1

 return ternarySearch(l, mid1 - 1, key, ar)

elif (key > ar[mid2]):

# The key lies in between mid2 and r

return ternarySearch(mid2 + 1, r, key, ar)

else:

# The key lies in between mid1 and mid2

return ternarySearch(mid1 + 1,
mid2 - 1, key, ar)

# Key not found

return -1

# Driver code
l, r, p = 0, 9, 5

# Get the array

# Sort the array if not sorted
ar = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]

# Starting index
l = 0

# end element index

r = 9

# Checking for 5

# Key to be searched in the array

key = 5

# Search the key using ternarySearch

p = ternarySearch(l, r, key, ar)

# Print the result

print("Index of", key, "is", p)

# Checking for 50

# Key to be searched in the array

key = 50

# Search the key using ternarySearch

p = ternarySearch(l, r, key, ar)

# Print the result

print("Index of", key, "is", p)
Output
Index of 5 is 4
Index of 50 is -1

Time Complexity: O(2 * log3n)

Auxiliary Space: O(log3n)
Iterative Approach of Ternary Search:

# Python 3 program to illustrate iterative

# approach to ternary search

# Function to perform Ternary Search

def ternarySearch(l, r, key, ar):
while r >= l:

# Find mid1 and mid2

mid1 = l + (r-l) // 3
mid2 = r - (r-l) // 3

# Check if key is at any mid

if key == ar[mid1]:
return mid1
if key == ar[mid2]:
return mid2

# Since key is not present at mid,

# Check in which region it is present
# Then repeat the search operation in that region
if key < ar[mid1]:
# key lies between l and mid1
r = mid1 - 1
elif key > ar[mid2]:
# key lies between mid2 and r
l = mid2 + 1
else:
# key lies between mid1 and mid2
l = mid1 + 1
r = mid2 - 1

# key not found

return -1

# Driver code

# Get the list

# Sort the list if not sorted
ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

# Starting index
l = 0

# end element index

r = 9

# Checking for 5
# Key to be searched in the list
key = 5

# Search the key using ternary search

p = ternarySearch(l, r, key, ar)

# Print the result

print("Index of", key, "is", p)

# Checking for 50
# Key to be searched in the list
key = 50

# Search the key using ternary search

p = ternarySearch(l, r, key, ar)

# Print the result

print("Index of", key, "is", p)

Output
Index of 5 is 4
Index of 50 is -1

Time Complexity: O(2 * log3n), where n is the size of the array.

Auxiliary Space: O(1)
Complexity Analysis of Ternary Search:
Time Complexity:
 Worst case: O(log3N)
 Average case: Θ(log3N)
 Best case: Ω(1)
Auxiliary Space: O(1)

Binary search Vs Ternary Search:

The time complexity of the binary search is less than the ternary
search as the number of comparisons in ternary search is much
more than binary search. Binary Search is used to find the
maxima/minima of monotonic functions where as Ternary Search is
used to find the maxima/minima of unimodal functions.
Note: We can also use ternary search for monotonic functions but the time complexity will be
slightly higher as compared to binary search.
Advantages:
 Ternary search can find maxima/minima for unimodal functions, where binary search is not
applicable.
 Ternary Search has a time complexity of O(2 * log3n), which is more efficient than linear
search and comparable to binary search.
 Fits well with optimization problems.
Disadvantages:
 Ternary Search is only applicable to ordered lists or arrays, and cannot be used on unordered
or non-linear data sets.
 Ternary Search takes more time to find maxima/minima of monotonic functions as compared
to Binary Search.
Summary:
 Ternary Search is a divide-and-conquer algorithm that is used to find the position of a
specific value in a given array or list.
 It works by dividing the array into three parts and recursively performing the search
operation on the appropriate part until the desired element is found.
 The algorithm has a time complexity of O(2 * log3n) and is more efficient than a linear
search, but less commonly used than other search algorithms like binary search.
 It’s important to note that the array to be searched must be sorted for Ternary Search to work
correctly.

Jump Search

Like Binary Search, Jump Search is a searching algorithm for sorted arrays. The basic idea is to
check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some
elements in place of searching all elements.
For example, suppose we have an array arr[] of size n and a block (to be jumped) of size m. Then
we search in the indexes arr[0], arr[m], arr[2m]…..arr[km], and so on. Once we find the interval
(arr[km] < x < arr[(k+1)m]), we perform a linear search operation from the index km to find the
element x.
Let’s consider the following array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). The
length of the array is 16. The Jump search will find the value of 55 with the following steps
assuming that the block size to be jumped is 4.

STEP 1: Jump from index 0 to index 4;

STEP 2: Jump from index 4 to index 8;
STEP 3: Jump from index 8 to index 12;
STEP 4: Since the element at index 12 is greater than 55, we will jump back a step to
come to index 8.
STEP 5: Perform a linear search from index 8 to get the element 55.
Performance in comparison to linear and binary search:
If we compare it with linear and binary search then it comes out then it is better than linear
search but not better than binary search.
The increasing order of performance is:
linear search < jump search < binary search
What is the optimal block size to be skipped?
In the worst case, we have to do n/m jumps, and if the last checked value is greater than the
element to be searched for, we perform m-1 comparisons more for linear search. Therefore, the
total number of comparisons in the worst case will be ((n/m) + m-1). The value of the function
((n/m) + m-1) will be minimum when m = ?n. Therefore, the best step size is m = ?n.
Algorithm steps
 Jump Search is an algorithm for finding a specific value in a sorted array by jumping through
certain steps in the array.
 The steps are determined by the sqrt of the length of the array.
 Here is a step-by-step algorithm for the jump search:
 Determine the step size m by taking the sqrt of the length of the array n.
 Start at the first element of the array and jump m steps until the value at that position is
greater than the target value.
Once a value greater than the target is found, perform a linear search starting from the
previous step until the target is found or it is clear that the target is not in the array.
If the target is found, return its index. If not, return -1 to indicate that the target was not found
in the array.
Example 1 :
Problem
Minimum Jumps
# Python3 code to implement Jump Search
import math

def jumpSearch( arr , x , n ):

# Finding block size to be jumped

step = math.sqrt(n)

# Finding the block where element is

# present (if it is present)
prev = 0
while arr[int(min(step, n)-1)] < x:
prev = step
step += math.sqrt(n)
if prev >= n:
return -1

# Doing a linear search for x in

# block beginning with prev.
while arr[int(prev)] < x:
prev += 1

# If we reached next block or end

# of array, element is not present.
 if prev == min(step, n):
return -1

# If element is found
if arr[int(prev)] == x:
return prev

return -1

# Driver code to test function

arr = [ 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610 ]
x = 55
n = len(arr)

# Find the index of 'x' using Jump Search

index = jumpSearch(arr, x, n)

# Print the index where 'x' is located

print("Number" , x, "is at index" ,"%.0f"%index)
Output:

Number 55 is at index 10

Time Complexity : O(n)

Auxiliary Space : O(1)
Advantages of Jump Search:
1. Better than a linear search for arrays where the elements are uniformly distributed.
2. Jump search has a lower time complexity compared to a linear search for large arrays.
3. The number of steps taken in jump search is proportional to the square root of the size of the
array, making it more efficient for large arrays.
4. It is easier to implement compared to other search algorithms like binary search or ternary
search.
5. Jump search works well for arrays where the elements are in order and uniformly distributed,
as it can jump to a closer position in the array with each iteration.
Important points:

 Works only with sorted arrays.

 The optimal size of a block to be jumped is (√ n). This makes the time complexity of Jump
Search O(√ n).
 The time complexity of Jump Search is between Linear Search ((O(n)) and Binary Search
(O(Log n)).
 Binary Search is better than Jump Search, but Jump Search has the advantage that we
traverse back only once (Binary Search may require up to O(Log n) jumps, consider a
situation where the element to be searched is the smallest element or just bigger than the
smallest). So, in a system where binary search is costly, we use Jump Search.
 Interpolation Search

Given a sorted array of n uniformly distributed values arr[], write a

function to search for a particular element x in the array.
Linear Search finds the element in O(n) time, Jump Search takes O(√ n) time and Binary
Search takes O(log n) time.
The Interpolation Search is an improvement over Binary Search for instances, where the values
in a sorted array are uniformly distributed. Interpolation constructs new data points within the
range of a discrete set of known data points. Binary Search always goes to the middle element to
check. On the other hand, interpolation search may go to different locations according to the
value of the key being searched. For example, if the value of the key is closer to the last element,
interpolation search is likely to start search toward the end side.
To find the position to be searched, it uses the following formula.
// The idea of formula is to return higher value of pos
// when element to be searched is closer to arr[hi]. And
// smaller value when closer to arr[lo]
arr[] ==> Array where elements need to be searched
x ==> Element to be searched
lo ==> Starting index in arr[]
hi ==> Ending index in arr[]

Problem
Binary Search
There are many different interpolation methods and one such is known as linear interpolation.
Linear interpolation takes two data points which we assume as (x1,y1) and (x2,y2) and the
formula is : at point(x,y).
This algorithm works in a way we search for a word in a dictionary. The interpolation search
algorithm improves the binary search algorithm. The formula for finding a value is: K = data-
low/high-low.

K is a constant which is used to narrow the search space. In the case of binary search, the value
for this constant is: K=(low+high)/2.

The formula for pos can be derived as follows.

Let's assume that the elements of the array are linearly distributed.
General equation of line : y = m*x + c.
y is the value in the array and x is its index.
Now putting value of lo,hi and x in the equation
arr[hi] = m*hi+c ----(1)
arr[lo] = m*lo+c ----(2)
x = m*pos + c ----(3)

m = (arr[hi] - arr[lo] )/ (hi - lo)

subtracting eqxn (2) from (3)

x - arr[lo] = m * (pos - lo)
lo + (x - arr[lo])/m = pos
pos = lo + (x - arr[lo]) *(hi - lo)/(arr[hi] - arr[lo])

Algorithm
The rest of the Interpolation algorithm is the same except for the above partition logic.
 Step1: In a loop, calculate the value of “pos” using the probe position formula.
 Step2: If it is a match, return the index of the item, and exit.
 Step3: If the item is less than arr[pos], calculate the probe position of the left sub-array.
Otherwise, calculate the same in the right sub-array.
 Step4: Repeat until a match is found or the sub-array reduces to zero.

Implementation of the algorithm.

# Python3 program to implement
# interpolation search
# with recursion

# If x is present in arr[0..n-1], then

# returns index of it, else returns -1.

def interpolationSearch(arr, lo, hi, x):

# Since array is sorted, an element present

# in array must be in range defined by corner
if (lo <= hi and x >= arr[lo] and x <= arr[hi]):

# Probing the position with keeping

# uniform distribution in mind.
pos = lo + ((hi - lo) // (arr[hi] - arr[lo]) *
(x - arr[lo]))

# Condition of target found

if arr[pos] == x:
return pos

# If x is larger, x is in right subarray

if arr[pos] < x:
return interpolationSearch(arr, pos + 1,
hi, x)

# If x is smaller, x is in left subarray

if arr[pos] > x:
return interpolationSearch(arr, lo,
pos - 1, x)
 return -1

# Driver code

# Array of items in which

# search will be conducted
arr = [10, 12, 13, 16, 18, 19, 20,
21, 22, 23, 24, 33, 35, 42, 47]
n = len(arr)

# Element to be searched
x = 18
index = interpolationSearch(arr, 0, n - 1, x)

if index != -1:
print("Element found at index", index)
else:
print("Element not found")

Output
Element found at index 4
Time Complexity: O(log2(log2 n)) for the average case, and O(n) for the worst case
Auxiliary Space Complexity: O(1)

Another approach:-
This is the iteration approach for the interpolation search.
 Step1: In a loop, calculate the value of “pos” using the probe position formula.
 Step2: If it is a match, return the index of the item, and exit.
 Step3: If the item is less than arr[pos], calculate the probe position of the left sub-array.
Otherwise, calculate the same in the right sub-array.
 Step4: Repeat until a match is found or the sub-array reduces to zero.

Below is the implementation of the algorithm.

# Python program to implement interpolation search by using iteration

approach
def interpolationSearch(arr, n, x):

# Find indexes of two corners

low = 0
high = (n - 1)
 # Since array is sorted, an element present
# in array must be in range defined by corner
while low <= high and x >= arr[low] and x <= arr[high]:
if low == high:
if arr[low] == x:
return low;
return -1;

# Probing the position with keeping

# uniform distribution in mind.
pos = int(low + (((float(high - low)/( arr[high] - arr[low]))
* (x - arr[low]))))

# Condition of target found

if arr[pos] == x:
return pos

# If x is larger, x is in upper part

if arr[pos] < x:
low = pos + 1;

# If x is smaller, x is in lower part

else:
high = pos - 1;

return -1

# Main function
if __name__ == "__main__":
# Array of items on whighch search will
# be conducted.
arr = [10, 12, 13, 16, 18, 19, 20, 21,
22, 23, 24, 33, 35, 42, 47]
n = len(arr)

x = 18 # Element to be searched
index = interpolationSearch(arr, n, x)

# If element was found

if index != -1:
print ("Element found at index",index)
else:
print ("Element not found")
Output
Element found at index 4
Time Complexity: O(log2(log2 n)) for the average case, and O(n) for the worst case
Auxiliary Space Complexity: O(1
 Exponential Search

The name of this searching algorithm may be misleading as it works in O(Log n) time. The name
comes from the way it searches an element.
Given a sorted array, and an element x to be
searched, find position of x in the array.

Input: arr[] = {10, 20, 40, 45, 55}

x = 45
Output: Element found at index 3

Input: arr[] = {10, 15, 25, 45, 55}

x = 15
Output: Element found at index 1

We have discussed, linear search, binary search for this problem.

Exponential search involves two steps:
1. Find range where element is present
2. Do Binary Search in above found range.
How to find the range where element may be present?
The idea is to start with subarray size 1, compare its last element with x, then try size 2, then 4
and so on until last element of a subarray is not greater.
Once we find an index i (after repeated doubling of i), we know that the element must be present
between i/2 and i (Why i/2) because we could not find a greater value in previous iteration)
Given below are the implementations of above steps.
# Python program to find an element x
# in a sorted array using Exponential Search

# A recursive binary search function returns

# location of x in given array arr[l..r] is
# present, otherwise -1
def binarySearch( arr, l, r, x):
if r >= l:
mid = l + ( r-l ) // 2

# If the element is present at

# the middle itself
if arr[mid] == x:
return mid

# If the element is smaller than mid,

# then it can only be present in the
# left subarray
if arr[mid] > x:
return binarySearch(arr, l,
mid - 1, x)

# Else he element can only be

 # present in the right
return binarySearch(arr, mid + 1, r, x)

# We reach here if the element is not present

return -1

# Returns the position of first

# occurrence of x in array
def exponentialSearch(arr, n, x):
# IF x is present at first
# location itself
if arr[0] == x:
return 0

# Find range for binary search

# j by repeated doubling
i = 1
while i < n and arr[i] <= x:
i = i * 2

# Call binary search for the found range

return binarySearch( arr, i // 2,
min(i, n-1), x)

# Driver Code
arr = [2, 3, 4, 10, 40]
n = len(arr)
x = 10
result = exponentialSearch(arr, n, x)
if result == -1:
print ("Element not found in the array")
else:
print ("Element is present at index %d" %(result))
Output
Element is present at index 3
Time Complexity : O(Log n)
Auxiliary Space : The above implementation of Binary Search is recursive and requires O(Log
n) space. With iterative Binary Search, we need only O(1) space.
Applications of Exponential Search:
1. Exponential Binary Search is particularly useful for unbounded searches, where size of array
is infinite. Please refer Unbounded Binary Search for an example.
2. It works better than Binary Search for bounded arrays, and also when the element to be
searched is closer to the first element.

Approach 2:
Iterative implementation
Here’s how it works:
 We start with an index i equal to 1 and repeatedly double it until either i is greater than or equal
to the length of the array or the value at index i is greater than or equal to the target value x.
We then perform a binary search on the range [i/2, min(i, n-1)], where n is the length of the
array. This range is guaranteed to contain the target value, if it is present in the array, because we
know that the target value must be greater than or equal to the value at index i/2 and less than or
equal to the value at index min(i, n-1).
If we find the target value in the binary search, we return its index. Otherwise, we return -1 to
indicate that the target value is not present in the array.
Python
def exponential_search(arr, x):
n = len(arr)
if n == 0:
return -1

# Find range for binary search by repeatedly doubling i

i = 1
while i < n and arr[i] < x:
i *= 2

# Perform binary search on the range [i/2, min(i, n-1)]

left = i // 2
right = min(i, n-1)

while left <= right:

mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1

return -1

# Driver Code
arr = [2, 3, 4, 10, 40]
n = len(arr)
x = 10
result = exponential_search(arr, x)
if result == -1:
print ("Element not found in the array")
else:
print ("Element is present at index %d" %(result))

Output
Element is present at index 3
Time Complexity : O(Log n)
Auxiliary Space : O(1) space.
Fibonacci Search
Given a sorted array arr[] of size n and an element x to be searched in it. Return index of x if it is
present in array else return -1.
Examples:
Input: arr[] = {2, 3, 4, 10, 40}, x = 10
Output: 3
Element x is present at index 3.
Input: arr[] = {2, 3, 4, 10, 40}, x = 11
Output: -1
Element x is not present.
Problem
Largest Fibonacci Subsequence
Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an
element in a sorted array.
Similarities with Binary Search:
1. Works for sorted arrays
2. A Divide and Conquer Algorithm.
3. Has Log n time complexity.
Differences with Binary Search:
1. Fibonacci Search divides given array into unequal parts
2. Binary Search uses a division operator to divide range. Fibonacci Search doesn’t use /, but
uses + and -. The division operator may be costly on some CPUs.
3. Fibonacci Search examines relatively closer elements in subsequent steps. So when the input
array is big that cannot fit in CPU cache or even in RAM, Fibonacci Search can be useful.
Background:
Fibonacci Numbers are recursively defined as F(n) = F(n-1) + F(n-2), F(0) = 0, F(1) = 1. First
few Fibonacci Numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Observations:
Below observation is used for range elimination, and hence for the O(log(n)) complexity.
F(n - 2) ≈ (1/3)*F(n) and
F(n - 1) ≈ (2/3)*F(n).
Algorithm:
Let the searched element be x.
The idea is to first find the smallest Fibonacci number that is greater than or equal to the length
of the given array. Let the found Fibonacci number be fib (m’th Fibonacci number). We use (m-
2)’th Fibonacci number as the index (If it is a valid index). Let (m-2)’th Fibonacci Number be i,
we compare arr[i] with x, if x is same, we return i. Else if x is greater, we recur for subarray after
i, else we recur for subarray before i.
Below is the complete algorithm
Let arr[0..n-1] be the input array and the element to be searched be x.
1. Find the smallest Fibonacci Number greater than or equal to n. Let this number be fibM
[m’th Fibonacci Number]. Let the two Fibonacci numbers preceding it be fibMm1 [(m-1)’th
Fibonacci Number] and fibMm2 [(m-2)’th Fibonacci Number].
2. While the array has elements to be inspected:

1. Compare x with the last element of the range covered by fibMm2

2. If x matches, return index
3. Else If x is less than the element, move the three Fibonacci variables two Fibonacci
down, indicating elimination of approximately rear two-third of the remaining array.
4. Else x is greater than the element, move the three Fibonacci variables one Fibonacci
down. Reset offset to index. Together these indicate the elimination of approximately
front one-third of the remaining array.
3. Since there might be a single element remaining for comparison, check if fibMm1 is 1. If
Yes, compare x with that remaining element. If match, return index.

# Python3 program for Fibonacci search.

from bisect import bisect_left

# Returns index of x if present, else

# returns -1

def fibMonaccianSearch(arr, x, n):

# Initialize fibonacci numbers

fibMMm2 = 0 # (m-2)'th Fibonacci No.
fibMMm1 = 1 # (m-1)'th Fibonacci No.
fibM = fibMMm2 + fibMMm1 # m'th Fibonacci

# fibM is going to store the smallest

# Fibonacci Number greater than or equal to n
while (fibM < n):
fibMMm2 = fibMMm1
fibMMm1 = fibM
fibM = fibMMm2 + fibMMm1

# Marks the eliminated range from front

offset = -1

# while there are elements to be inspected.

# Note that we compare arr[fibMm2] with x.
# When fibM becomes 1, fibMm2 becomes 0
while (fibM > 1):

# Check if fibMm2 is a valid location

i = min(offset+fibMMm2, n-1)

# If x is greater than the value at

# index fibMm2, cut the subarray array
# from offset to i
if (arr[i] < x):
fibM = fibMMm1
fibMMm1 = fibMMm2
 fibMMm2 = fibM - fibMMm1
offset = i

# If x is less than the value at

# index fibMm2, cut the subarray
# after i+1
elif (arr[i] > x):
fibM = fibMMm2
fibMMm1 = fibMMm1 - fibMMm2
fibMMm2 = fibM - fibMMm1

# element found. return index

else:
return i

# comparing the last element with x */

if(fibMMm1 and arr[n-1] == x):
return n-1

# element not found. return -1

return -1

# Driver Code
arr = [10, 22, 35, 40, 45, 50,
80, 82, 85, 90, 100,235]
n = len(arr)
x = 235
ind = fibMonaccianSearch(arr, x, n)
if ind>=0:
print("Found at index:",ind)
else:
print(x,"isn't present in the array");

Output
Found at index: 11
Illustration:
Let us understand the algorithm with the below example:

Illustration assumption: 1-based indexing. Target element x is 85. Length of array n = 11.
Smallest Fibonacci number greater than or equal to 11 is 13. As per our illustration, fibMm2 = 5,
fibMm1 = 8, and fibM = 13.
Another implementation detail is the offset variable (zero-initialized). It marks the range that has
been eliminated, starting from the front. We will update it from time to time.
Now since the offset value is an index and all indices including it and below it have been
eliminated, it only makes sense to add something to it. Since fibMm2 marks approximately one-
third of our array, as well as the indices it marks, are sure to be valid ones, we can add fibMm2
to offset and check the element at index i = min(offset + fibMm2, n).

Visualization:

Time Complexity analysis:

The worst-case will occur when we have our target in the larger (2/3) fraction of the array, as we
proceed to find it. In other words, we are eliminating the smaller (1/3) fraction of the array every
time. We call once for n, then for(2/3) n, then for (4/9) n, and henceforth.
Consider that:
Auxiliary Space: O(1)
Approach 2: Iterative implementation
Fibonacci Search is a searching algorithm used to find the position of an element in a sorted
array. The basic idea behind Fibonacci Search is to use Fibonacci numbers to determine the split
points in the array and perform binary search on the appropriate subarray.

Here’s a Python implementation of Fibonacci Search using an

iterative approach:
Python
def fibonacci_search(arr, x):
n = len(arr)
if n == 0:
return -1

# Initialize Fibonacci numbers

fib1, fib2 = 0, 1
fib3 = fib1 + fib2

# Find the smallest Fibonacci number greater than or equal to n

while fib3 < n:
fib1, fib2 = fib2, fib3
fib3 = fib1 + fib2

# Initialize variables for the current and previous split points

offset = -1
while fib3 > 1:
i = min(offset + fib2, n-1)

# If x is greater than the value at index i, move the split

point to the right
if arr[i] < x:
fib3 = fib2
fib2 = fib1
fib1 = fib3 - fib2
offset = i

# If x is less than the value at index i, move the split point

to the left
elif arr[i] > x:
fib3 = fib1
 fib2 = fib2 - fib1
fib1 = fib3 - fib2

# If x is equal to the value at index i, return the index

else:
return i

# If x is not found in the array, return -1

if fib2 == 1 and arr[offset+1] == x:
return offset + 1
else:
return -1

# Driver Code
arr = [10, 22, 35, 40, 45, 50,
80, 82, 85, 90, 100,235]
n = len(arr)
x = 235
ind = fibonacci_search(arr, x)
if ind>=0:
print("Found at index:",ind)
else:
print(x,"isn't present in the array");

Output
Found at index: 11
The time complexity of Fibonacci Search is O(log n), where n is the length of the input array.
This is because at each iteration of the algorithm, the search range is reduced by a factor of
approximately 1/φ, where φ is the golden ratio (φ ≈ 1.618). The number of iterations required to
reduce the search range to a single element is approximately logₑ(n), where logₑ denotes the
natural logarithm.
Since each iteration of Fibonacci Search requires constant time, the overall time complexity of
the algorithm is O(log n). This makes Fibonacci Search a faster algorithm than linear search, but
slower than binary search and other logarithmic search algorithms such as interpolation search
and exponential search.
Auxiliary Space: O(1)
The Ubiquitous Binary Search | Set 1
We are aware of the binary search algorithm. Binary search is the easiest algorithm to get right. I
present some interesting problems that I collected on binary search. There were some requests on
binary search. I request you to honor the code, “I sincerely attempt to solve the problem and
ensure there are no corner cases”. After reading each problem, minimize the browser and
try solving it.
Problem Statement: Given a sorted array of N distinct elements, find a key in the array using
the least number of comparisons. (Do you think binary search is optimal to search a key in sorted
array?) Without much theory, here is typical binary search algorithm.
Python
# Returns location of key, or -1 if not found
def BinarySearch(A, l, r, key):
while (l < r):
m = l + (r - l) // 2
if A[m] == key: #first comparison
return m
if A[m] < key: # second comparison
l = m + 1
else:
r = m - 1
return -1

Theoretically we need log N + 1 comparisons in worst case. If we observe, we are using two
comparisons per iteration except during final successful match, if any. In practice, comparison
would be costly operation, it won’t be just primitive type comparison. It is more economical to
minimize comparisons as that of theoretical limit. See below figure on initialize of indices in the
next implementation.

The following implementation uses fewer number of comparisons.

Python
# Invariant: A[l] <= key and A[r] > key
# Boundary: |r - l| = 1
# Input: A[l .... r-1]

def BinarySearch(A, l, r, key):

while (r-l > 1):
m = l+(r-l)//2
if A[m] <= key:
l = m
else:
r = m
 if A[l] == key:
return l
if A[r] == key:
return r
return -1

In the while loop we are depending only on one comparison. The search space converges to
place l and r point two different consecutive elements.

Problem Statement:
Given an array of N distinct integers, find floor value of input ‘key’. Say, A = {-1, 2, 3, 5, 6, 8, 9,
10} and key = 7, we should return 6 as outcome. We can use the above optimized
implementation to find floor value of key. We keep moving the left pointer to right most as long
as the invariant holds. Eventually left pointer points an element less than or equal to key (by
definition floor value). The following are possible corner cases, —> If all elements in the array
are smaller than key, left pointer moves till last element. —> If all elements in the array are
greater than key, it is an error condition. —> If all elements in the array equal and <= key, it is
worst case input to our implementation.
Here is implementation,
Python
# largest value <= key
# Invariant: A[l] <= key and A[r] > key
# Boundary: |r - l| = 1
# Input: A[l .... r-1]
# Precondition: A[l] <= key <= A[r]
def Floor(A,l,r,key):
while (r-l>1):
m=l+(r-l)//2
if A[m]<=key:
l=m
else:
r=m
return A[l]
# Initial call
def Floor(A,size,key):
# Add error checking if key < A[0]
if key<A[0]:
return -1
# Observe boundaries
return Floor(A,0,size,key)

Problem Statement:
Given a sorted array with possible duplicate elements. Find number of occurrences of input ‘key’
in log N time. The idea here is finding left and right most occurrences of key in the array using
binary search. We can modify floor function to trace right most occurrence and left most
occurrence.
Here is implementation,

# Input: Indices Range [l ... r)

# Invariant: A[l] <= key and A[r] > key

def GetRightPosition(A,l,r,key):
while r-l>1:
m=l+(r-l)//2
if A[m]<=key:
l=m
else:
r=m
return l
# Input: Indices Range (l ... r]
# Invariant: A[r] >= key and A[l] > key
def GetLeftPosition(A,l,r,key):
while r-l>1:
m=l+(r-l)//2
if A[m]>=key:
r=m
else:
l=m
return r
def countOccurrences(A,size,key):
#Observe boundary conditions
left=GetLeftPosition(A,-1,size-1,key)
right=GetRightPosition(A,0,size,key)
# What if the element doesn't exists in the array?
# The checks helps to trace that element exists

if A[left]==key and key==A[right]:

return right-left+1
return 0
Problem Statement: Given a sorted array of distinct elements, and the array is rotated at an
unknown position. Find minimum element in the array. We can see pictorial representation of
sample input array in the below figure.
We converge the search space till l and r points single element. If
the middle location falls in the first pulse, the condition A[m] < A[r]
doesn’t satisfy, we converge our search space to A[m+1 … r]. If the
middle location falls in the second pulse, the condition A[m] < A[r]
satisfied, we converge our search space to A[1 … m]. At every
iteration we check for search space size, if it is 1, we are done.
Given below is implementation of algorithm.

def BinarySearchIndexOfMinimumRotatedArray(A, l, r):

# extreme condition, size zero or size two
# Precondition: A[l] > A[r]
if A[l] >= A[r]:
return l
while (l <= r):
# Termination condition (l will eventually falls on r, and r
always
# point minimum possible value)
if l == r:
return l
m = l+(r-l)//2 # 'm' can fall in first pulse,
# second pulse or exactly in the middle
if A[m] < A[r]:
# min can't be in the range
# (m < i <= r), we can exclude A[m+1 ... r]
r = m
else:
# min must be in the range (m < i <= r),
# we must search in A[m+1 ... r]

l = m+1
return -1
def BinarySearchIndexOfMinimumRotatedArray(A, size):
return BinarySearchIndexOfMinimumRotatedArray(A, 0, size-1)

Exercises:
1. A function called signum(x, y) is defined as,

signum(x, y) = -1 if x < y
= 0 if x = y
= 1 if x > y

the signum function is a common way to express the result of a comparison operation, and it
aligns with how many comparison instructions and functions work in various programming
languages and instruction sets.

Understanding the signum Function

The signum function, defined as:

 -1 if x<yx < yx<y

 0 if x=yx = yx=y
 1 if x>yx > yx>y

This function essentially captures the outcome of a comparison between two values in a compact
form, which is useful in many algorithms and programming contexts.

Comparison Instructions and signum

In many programming languages and instruction sets, comparison operations result in boolean
values or integer codes that can be used similarly to the signum function:

1. Python:
o In Python, you can use a simple function to achieve the same:

def signum(x, y):

return (x > y) - (x < y)

Binary Search Optimization

Using a signum-like comparison function can indeed simplify and potentially optimize the
implementation of binary search:

Traditional Binary Search

In a typical binary search algorithm, you have:

  A comparison of the middle element with the target value.
 Based on whether the middle element is less than, equal to, or greater than the target, you
adjust the search range.

Example:

def binary_search(arr, target):

low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] < target:
low = mid + 1
elif arr[mid] > target:
high = mid - 1
else:
return mid
return -1

Using a signum Function

If you define a signum function for comparison, you can streamline the comparison logic:

Example:

def signum(x, y):

return (x > y) - (x < y)

def binary_search(arr, target):

low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
result = signum(arr[mid], target)
if result < 0:
low = mid + 1
elif result > 0:
high = mid - 1
else:
return mid
return -1

Python script that incorporates user input to perform a binary search using the signum function:

def signum(x, y):

return (x > y) - (x < y)

def binary_search(arr, target):

low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
result = signum(arr[mid], target)
if result < 0:
low = mid + 1
elif result > 0:
high = mid - 1
 else:
return mid
return -1

def main():
# User input for the array
arr_input = input("Enter the sorted array elements separated by spaces: ")
arr = list(map(int, arr_input.split()))

# User input for the target value

target = int(input("Enter the target value: "))

# Perform binary search

index = binary_search(arr, target)

# Output the result

if index != -1:
print(f"Element {target} found at index {index}.")
else:
print(f"Element {target} not found in the array.")

if __name__ == "__main__":
main()

Explanation:

1. signum(x, y): This function returns -1, 0, or 1 based on the comparison between x and
y.
2. binary_search(arr, target): This function performs a binary search using the
signum function to compare elements. It returns the index of the target if found,
otherwise -1.
3. main():
o Prompts the user to input a sorted array and target value.
o Converts the array input into a list of integers.
o Calls binary_search with the user-provided array and target.
o Outputs the result indicating whether the target was found and its index.

To run the script, copy the code into a Python file and execute it. It will ask for user input and
perform the binary search based on the input values.

Benefits

1. Code Clarity: Using a signum function can make the comparison logic more explicit and
easier to understand, especially when dealing with multiple comparisons.
2. Optimization: Some low-level optimizations can be applied if the comparison results are
standardized, as it simplifies branching and can be used to directly drive search decisions.

Conclusion
The signum function provides a clear and concise way to handle comparisons and can simplify
the implementation of binary search algorithms. While most modern programming languages
and systems support efficient comparison operations natively, adopting a signum-like approach
can still help in understanding and implementing algorithms more clearly.

Python for these examples.

1. Linear Search

Description: This algorithm checks each element in a list sequentially until the target element is
found.

def linear_search(arr, target):

for index, value in enumerate(arr):
if value == target:
return index
return -1

# Example usage
arr = [5, 3, 7, 2, 8]
target = int(input("Enter the number to search for: "))
index = linear_search(arr, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

2. Sentinel Linear Search

Description: This is a modification of linear search where a sentinel value is placed at the end of
the list to avoid the need for a boundary check.

def sentinel_linear_search(arr, target):

n = len(arr)
last = arr[-1]
arr[-1] = target
i = 0
while arr[i] != target:
i += 1
arr[-1] = last
if i < n - 1 or arr[-1] == target:
return i
return -1

# Example usage
arr = [5, 3, 7, 2, 8]
target = int(input("Enter the number to search for: "))
index = sentinel_linear_search(arr, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

3. Binary Search

Description: This algorithm works on sorted arrays by repeatedly dividing the search interval in
half.
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

# Example usage
arr = sorted([5, 3, 7, 2, 8])
target = int(input("Enter the number to search for: "))
index = binary_search(arr, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

4. Meta Binary Search | One-Sided Binary Search

Description: This is a variant of binary search where only one side of the array is searched based
on the comparison.

def one_sided_binary_search(arr, target):

left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
if arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

# Example usage
arr = sorted([5, 3, 7, 2, 8])
target = int(input("Enter the number to search for: "))
index = one_sided_binary_search(arr, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

5. Ternary Search

Description: This search algorithm divides the array into three parts and reduces the search
interval based on comparisons.

def ternary_search(arr, left, right, target):

if right >= left:
mid1 = left + (right - left) // 3
mid2 = right - (right - left) // 3
if arr[mid1] == target:
return mid1
if arr[mid2] == target:
return mid2
 if target < arr[mid1]:
return ternary_search(arr, left, mid1 - 1, target)
elif target > arr[mid2]:
return ternary_search(arr, mid2 + 1, right, target)
else:
return ternary_search(arr, mid1 + 1, mid2 - 1, target)
return -1

# Example usage
arr = sorted([5, 3, 7, 2, 8])
target = int(input("Enter the number to search for: "))
index = ternary_search(arr, 0, len(arr) - 1, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

6. Jump Search

Description: This algorithm jumps ahead by fixed steps and performs a linear search in the
block where the element might be.

import math

def jump_search(arr, target):

n = len(arr)
step = int(math.sqrt(n))
prev = 0
while arr[min(step, n) - 1] < target:
prev = step
step += int(math.sqrt(n))
if prev >= n:
return -1
for i in range(prev, min(step, n)):
if arr[i] == target:
return i
return -1

# Example usage
arr = sorted([5, 3, 7, 2, 8])
target = int(input("Enter the number to search for: "))
index = jump_search(arr, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

7. Interpolation Search

Description: This algorithm estimates the position of the target element based on the values of
the elements at the ends of the array.

def interpolation_search(arr, target):

low, high = 0, len(arr) - 1
while low <= high and target >= arr[low] and target <= arr[high]:
pos = low + ((target - arr[low]) * (high - low) // (arr[high] -
arr[low]))
if arr[pos] == target:
return pos
if arr[pos] < target:
 low = pos + 1
else:
high = pos - 1
return -1

# Example usage
arr = sorted([5, 3, 7, 2, 8])
target = int(input("Enter the number to search for: "))
index = interpolation_search(arr, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

8. Exponential Search

Description: This algorithm finds the range where the target might be and then performs binary
search in that range.

def exponential_search(arr, target):

if arr[0] == target:
return 0
index = 1
while index < len(arr) and arr[index] <= target:
index *= 2
return binary_search(arr[min(index // 2, len(arr) - 1):min(index,
len(arr))], target) + min(index // 2, len(arr) - 1) if index < len(arr) else
binary_search(arr[index // 2:], target) + index // 2

# Example usage
arr = sorted([5, 3, 7, 2, 8])
target = int(input("Enter the number to search for: "))
index = exponential_search(arr, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

9. Fibonacci Search

Description: This algorithm uses Fibonacci numbers to determine the block size and performs
search within that block.

def fibonacci_search(arr, target):

fib_m_2, fib_m_1 = 0, 1
fib_m = fib_m_1 + fib_m_2
while fib_m < len(arr):
fib_m_2 = fib_m_1
fib_m_1 = fib_m
fib_m = fib_m_1 + fib_m_2

offset = -1
while fib_m > 1:
i = min(offset + fib_m_2, len(arr) - 1)
if arr[i] < target:
fib_m = fib_m_1
fib_m_1 = fib_m_2
fib_m_2 = fib_m - fib_m_1
offset = i
elif arr[i] > target:
 fib_m = fib_m_2
fib_m_1 -= fib_m_2
fib_m_2 = fib_m - fib_m_1
else:
return i

if fib_m_1 and arr[offset + 1] == target:

return offset + 1
return -1

# Example usage
arr = sorted([5, 3, 7, 2, 8])
target = int(input("Enter the number to search for: "))
index = fibonacci_search(arr, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

10. The Ubiquitous Binary Search

Description: This refers to the standard binary search algorithm mentioned before, but it's
named here for its frequent usage.

def ubiquitous_binary_search(arr, target):

return binary_search(arr, target)

# Example usage
arr = sorted([5, 3, 7, 2, 8])
target = int(input("Enter the number to search for: "))
index = ubiquitous_binary_search(arr, target)
print(f"Element found at index {index}" if index != -1 else "Element not
found")

1. Linear Search

Description: Linear search is the simplest search algorithm. It works by checking each element
of a list or array sequentially from the start to the end until the target element is found or the end
of the list is reached.

Time Complexity: O(n), where n is the number of elements in the array.

How It Works:

1. Start from the first element of the array.

2. Compare the current element with the target element.
3. If they match, return the index.
4. If not, move to the next element.
5. If you reach the end of the array without finding the target, return -1.

Use Case: Linear search is useful when the array is unsorted or very small.

2. Sentinel Linear Search

Description: Sentinel linear search is an optimization of the linear search algorithm. It avoids
checking the boundary condition (whether the end of the array is reached) by placing a sentinel
value at the end of the array.

Time Complexity: O(n) but it can be faster than linear search in practice since it avoids
checking boundary conditions.

How It Works:

1. Replace the last element of the array with the target element.
2. Proceed with a standard linear search.
3. Once the target is found, check if it was found in the original last position or if it was
actually in the array.

Use Case: Useful for slightly optimizing linear search in arrays.

3. Binary Search

Description: Binary search is an efficient algorithm for finding an element in a sorted array. It
repeatedly divides the search interval in half, comparing the target with the middle element of the
interval.

Time Complexity: O(logn), where n is the number of elements in the array.

How It Works:

1. Start with the entire array.

2. Find the middle element.
3. Compare the middle element with the target:
o If equal, return the index.
o If the target is smaller, narrow the search to the left half.
o If the target is larger, narrow the search to the right half.
4. Repeat until the target is found or the interval is empty.

Use Case: Ideal for large, sorted arrays.

4. Meta Binary Search | One-Sided Binary Search

Description: One-sided binary search is a variant of binary search. It focuses on only one side of
the array based on the comparison result, which can be useful in certain scenarios where one side
of the array is more likely to contain the target.

Time Complexity: O(logn), similar to binary search.

How It Works:

1. Use binary search, but decide which side of the array to search based on the comparison
between the target and the middle element.
 2. If the target is greater or smaller, you search only one side, ignoring the other side.

Use Case: Useful when there's a reason to believe that the target is more likely in one part of the
array.

5. Ternary Search

Description: Ternary search divides the array into three parts instead of two, reducing the search
interval more quickly.

Time Complexity:O(log3n), which is more efficient than binary search for some cases.

How It Works:

1. Divide the array into three parts by two midpoints.

2. Compare the target with these midpoints:
o If it matches, return the index.
o If the target is less than the first midpoint, search the left part.
o If the target is greater than the second midpoint, search the right part.
o Otherwise, search the middle part.
3. Repeat until the target is found or the interval is empty.

Use Case: Useful in situations where you want to reduce the search space more quickly.

6. Jump Search

Description: Jump search improves on linear search by jumping ahead by fixed steps and then
performing a linear search within the block where the target might be.

Time Complexity: O(√n), where n is the number of elements in the array.

How It Works:

1. Determine a block size (usually n\√n).

2. Jump ahead by this block size until you either find the target or exceed the array bounds.
3. Perform a linear search within the last block where the target could be.

Use Case: Suitable for sorted arrays where you want a trade-off between linear and binary
search.

7. Interpolation Search

Description: Interpolation search estimates the position of the target based on the values of the
elements at the ends of the array. It’s useful when the values are uniformly distributed.

Time Complexity: O(log log n) on average, but can degrade to O(n) in the worst case.
How It Works:

1. Estimate the position of the target based on its value relative to the values at the ends of
the array.
2. Compare the estimated position's value with the target:
o If equal, return the index.
o If less, narrow the search to the right.
o If more, narrow the search to the left.
3. Repeat until the target is found or the interval is empty.

Use Case: Works well when elements are uniformly distributed.

8. Exponential Search

Description: Exponential search finds the range where the target might be by expanding
exponentially, and then performs binary search within that range.

Time Complexity:O(logn), where nnn is the number of elements in the array.

How It Works:

1. Start with the first element and exponentially increase the index (1, 2, 4, 8, etc.) until you
either find the target or exceed the array bounds.
2. Perform binary search within the range defined by the last index and the current index.

Use Case: Suitable for unbounded or infinite-sized arrays.

9. Fibonacci Search

Description: Fibonacci search uses Fibonacci numbers to determine the block size for searching,
which helps in narrowing down the search area more efficiently than binary search in some
cases.

Time Complexity: O(logn), similar to binary search.

How It Works:

1. Determine the largest Fibonacci number less than the length of the array.
2. Use this Fibonacci number to divide the array and reduce the search interval.
3. Repeat the process by adjusting the Fibonacci numbers until the target is found.

Use Case: Useful when dividing the array into chunks based on Fibonacci numbers can be
advantageous.

10. The Ubiquitous Binary Search

Description: This refers to the standard binary search algorithm, emphasizing its common usage
and applicability.

Time Complexity: O(logn), same as binary search.

How It Works:

1. Divide the array into two halves and compare the middle element with the target.
2. Narrow down the search to the left or right half based on the comparison.
3. Continue until the target is found or the search interval is empty.

Use Case: Most common search algorithm for sorted arrays, widely applicable and efficient.

These explanations cover the basic concepts and use cases for each search algorithm. Let me
know if you need more details on any specific one!

search algorithm depends on various factors including the characteristics of the dataset and the
specific use case. Here’s a summary to help you choose the best search algorithm for different
scenarios:

1. Linear Search

 Best For: Unsorted or small arrays where simplicity is preferred.

 Pros: Simple and doesn’t require sorted data.
 Cons: Inefficient for large datasets as it has O(n) time complexity.

2. Sentinel Linear Search

 Best For: Slightly optimizing linear search, especially when the search operation is
performed frequently.
 Pros: Avoids boundary checks during the search.
 Cons: Still has O(n) time complexity and is only a minor optimization.

3. Binary Search

 Best For: Large, sorted arrays.

 Pros: Efficient with O(\log n) time complexity.
 Cons: Requires the data to be sorted beforehand.

4. Meta Binary Search | One-Sided Binary Search

 Best For: Scenarios where the target is known to be more likely in one part of the array.
 Pros: Efficient if you have additional knowledge about where the target might be.
 Cons: Less general applicability than standard binary search.

5. Ternary Search
  Best For: Sorted arrays where reducing the search space faster is beneficial.
 Pros: Reduces the search space faster than binary search.
 Cons: More complex and only marginally more efficient in practice compared to binary
search.

6. Jump Search

 Best For: Sorted arrays where a trade-off between linear and binary search is desired.
 Pros: O(√n) time complexity can be faster than linear search for large datasets.
 Cons: Requires pre-determined block size and still not as efficient as binary search for
very large arrays.

7. Interpolation Search

 Best For: Sorted arrays with uniformly distributed values.

 Pros: Can be faster than binary search if values are uniformly distributed.
 Cons: Performance can degrade if the data is not uniformly distributed.

8. Exponential Search

 Best For: Large or infinite-sized sorted arrays.

 Pros: Combines exponential exploration with binary search for efficient searching.
 Cons: Can be overkill for smaller arrays.

9. Fibonacci Search

 Best For: Sorted arrays where dividing the array using Fibonacci numbers is
advantageous.
 Pros: Efficient like binary search with O(log n) complexity.
 Cons: More complex and less commonly used in practice.

10. The Ubiquitous Binary Search

 Best For: General-purpose searching in sorted arrays.

 Pros: Standard, widely used, and efficient with O(logn) time complexity.
 Cons: Requires sorted data.

Choosing the Best Algorithm

 Unsorted Data: Use linear search.

 Sorted Data: Use binary search or exponential search for large datasets. If you have
knowledge of the distribution or characteristics of the data, other algorithms like
interpolation or Fibonacci search might be advantageous.
 Uniform Distribution: Interpolation search can be more efficient than binary search.
 Infinite or Very Large Data: Exponential search is suitable when the size of the data is
not known beforehand.
Ultimately, the choice depends on your specific needs, such as whether the data is sorted, the
size of the dataset, and any additional knowledge you have about the data distribution. For
general use, binary search is often the best choice due to its efficiency and simplicity.

Time measure function

import time
import random

# Generate a large sorted list

large_list = sorted([random.randint(1, 1000000) for _ in
range(1000000)])
target = random.choice(large_list)

# Linear Search Function

def linear_search(arr, target):
for index, value in enumerate(arr):
if value == target:
return index
return -1

# Sentinel Linear Search Function

def sentinel_linear_search(arr, target):
n = len(arr)
last = arr[-1]
arr[-1] = target
i = 0
while arr[i] != target:
i += 1
arr[-1] = last
if i < n - 1 or arr[-1] == target:
return i
return -1

# Binary Search Function

def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1

# Ternary Search Function

def ternary_search(arr, left, right, target):
 if right >= left:
mid1 = left + (right - left) // 3
mid2 = right - (right - left) // 3
if arr[mid1] == target:
return mid1
if arr[mid2] == target:
return mid2
if target < arr[mid1]:
return ternary_search(arr, left, mid1 - 1, target)
elif target > arr[mid2]:
return ternary_search(arr, mid2 + 1, right, target)
else:
return ternary_search(arr, mid1 + 1, mid2 - 1, target)
return -1

# Jump Search Function

def jump_search(arr, target):
import math
n = len(arr)
step = int(math.sqrt(n))
prev = 0
while arr[min(step, n) - 1] < target:
prev = step
step += int(math.sqrt(n))
if prev >= n:
return -1
for i in range(prev, min(step, n)):
if arr[i] == target:
return i
return -1

# Interpolation Search Function

def interpolation_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high and target >= arr[low] and target <= arr[high]:
pos = low + ((target - arr[low]) * (high - low) // (arr[high]
- arr[low]))
if arr[pos] == target:
return pos
if arr[pos] < target:
low = pos + 1
else:
high = pos - 1
return -1

# Exponential Search Function

def exponential_search(arr, target):
if arr[0] == target:
return 0
index = 1
 while index < len(arr) and arr[index] <= target:
index *= 2
return binary_search(arr[min(index // 2, len(arr) - 1):min(index,
len(arr))], target) + min(index // 2, len(arr) - 1) if index <
len(arr) else binary_search(arr[index // 2:], target) + index // 2

# Fibonacci Search Function

def fibonacci_search(arr, target):
def fib_m(n):
if n == 0: return 0
elif n == 1: return 1
else:
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b

n = len(arr)
fib_m_2 = 0
fib_m_1 = 1
fib_m = fib_m_1 + fib_m_2

while fib_m < n:

fib_m_2 = fib_m_1
fib_m_1 = fib_m
fib_m = fib_m_1 + fib_m_2

offset = -1
while fib_m > 1:
i = min(offset + fib_m_2, n - 1)
if arr[i] < target:
fib_m = fib_m_1
fib_m_1 = fib_m_2
fib_m_2 = fib_m - fib_m_1
offset = i
elif arr[i] > target:
fib_m = fib_m_2
fib_m_1 -= fib_m_2
fib_m_2 = fib_m - fib_m_1
else:
return i

if fib_m_1 and arr[offset + 1] == target:

return offset + 1
return -1

# Timing Function
def measure_time(func, *args, iterations=10):
total_time = 0
for _ in range(iterations):
 start_time = time.perf_counter()
func(*args)
end_time = time.perf_counter()
total_time += (end_time - start_time)
average_time = total_time / iterations
return average_time

# Measure Time for Each Search Algorithm

iterations = 10 # Number of iterations for averaging

# Linear Search
linear_search_time = measure_time(linear_search, large_list, target,
iterations=iterations)
print(f"Linear Search took {linear_search_time:.6f} seconds")

# Sentinel Linear Search

sentinel_linear_search_time = measure_time(sentinel_linear_search,
large_list, target, iterations=iterations)
print(f"Sentinel Linear Search took {sentinel_linear_search_time:.6f}
seconds")

# Binary Search
binary_search_time = measure_time(binary_search, large_list, target,
iterations=iterations)
print(f"Binary Search took {binary_search_time:.6f} seconds")

# Ternary Search
ternary_search_time = measure_time(ternary_search, large_list, 0,
len(large_list) - 1, target, iterations=iterations)
print(f"Ternary Search took {ternary_search_time:.6f} seconds")

# Jump Search
jump_search_time = measure_time(jump_search, large_list, target,
iterations=iterations)
print(f"Jump Search took {jump_search_time:.6f} seconds")

# Interpolation Search
interpolation_search_time = measure_time(interpolation_search,
large_list, target, iterations=iterations)
print(f"Interpolation Search took {interpolation_search_time:.6f}
seconds")

# Exponential Search
exponential_search_time = measure_time(exponential_search, large_list,
target, iterations=iterations)
print(f"Exponential Search took {exponential_search_time:.6f}
seconds")

# Fibonacci Search
fibonacci_search_time = measure_time(fibonacci_search, large_list,
target, iterations=iterations)
print(f"Fibonacci Search took {fibonacci_search_time:.6f} seconds")

The measure_time function is designed to provide accurate timing measurements by executing a

search algorithm multiple times and averaging the results. Here’s a detailed explanation of how it
works:

measure_time Function Explanation

def measure_time(func, *args, iterations=10):
total_time = 0
for in range(iterations):
start_time = time.perf_counter() # Record the start time
func(*args) # Call the search function with arguments
end_time = time.perf_counter() # Record the end time
total_time += (end_time - start_time) # Accumulate the time taken
average_time = total_time / iterations # Calculate the average time
return average_time

Parameters

 func: The search function you want to measure (e.g., linear_search or

binary_search).
 *args: Arguments passed to the search function. This allows you to use measure_time
with any function that takes parameters.
 iterations: Number of times to run the search function to get a stable average time.
Default is 10.

Steps

1. Initialize total_time:
o Start with total_time set to 0 to accumulate the total time taken over all
iterations.
2. Loop for Specified Iterations:
o For each iteration, record the start time using time.perf_counter(). This
function provides a high-resolution timer suitable for measuring short durations.
o Call the search function (func(*args)) with the provided arguments.
o Record the end time after the function call.
o Compute the time taken for that iteration by subtracting start_time from
end_time.
o Add this duration to total_time.
3. Calculate Average Time:
o After completing all iterations, compute the average time by dividing total_time
by the number of iterations.
4. Return the Average Time:
 o The function returns the average time, providing a more stable and accurate
measurement than a single execution.

Example with Linear and Binary Search

Here’s how you would use measure_time to measure the time for linear search and binary
search:

# Measure Time for Linear Search

linear_search_time = measure_time(linear_search, large_list, target,
iterations=10)
print(f"Linear Search took {linear_search_time:.6f} seconds")

# Measure Time for Binary Search

binary_search_time = measure_time(binary_search, large_list, target,
iterations=10)
print(f"Binary Search took {binary_search_time:.6f} seconds")

Explanation of Example

1. Linear Search:
o measure_time is called with linear_search as the function and large_list
and target as arguments.
o It runs linear_search 10 times, measures the time for each run, and calculates
the average time taken.
2. Binary Search:
o measure_time is called with binary_search as the function and large_list
and target as arguments.
o Similarly, it runs binary_search 10 times and calculates the average execution
time.

Why Multiple Iterations?

Running the search function multiple times helps to:

 Smooth Out Variability: Reduces the impact of random fluctuations or system load on
the measurement.
 Provide a Reliable Metric: Average time is more representative of the typical
performance of the search algorithm.

By following this approach, you get a precise measurement of the time taken by each search
algorithm, making it easier to compare their performance effectively.

An iteration refers to a single execution of a repetitive process or loop within a program. In the
context of timing functions or algorithms, iterations are often used to repeatedly execute a piece
of code to gather data, improve accuracy, or achieve a specific objective.

Key Points About Iterations

 1. Basic Concept:
o In programming, an iteration is one complete pass through a loop. For example, if
you have a for loop or a while loop, each time the loop body executes, that is
one iteration.
2. Purpose in Timing:
o When measuring the performance of a function or algorithm, iterations are used to
repeatedly run the function. This helps to average out the execution time,
providing a more accurate measure by reducing the impact of variability.
3. Example in Context:
o If you want to measure how long a sorting algorithm takes to sort a list, you might
run the sorting function multiple times (iterations) and calculate the average time.
This is because a single run might be influenced by temporary system load or
other factors, leading to inconsistent results.

Example of Iteration in a Loop

Here’s a simple example of a loop with iterations in Python:

for i in range(5): # Loop runs 5 times

print(f"Iteration {i + 1}")

In this example:

 The for loop will iterate 5 times.

 On each iteration, it prints the current iteration number.

Example of Iterations in Timing

In the context of timing functions, you might use iterations like this:

import time

def example_function():
# Code to measure
pass

def measure_time(func, iterations=10):

total_time = 0
for _ in range(iterations):
start_time = time.perf_counter()
func() # Call the function
end_time = time.perf_counter()
total_time += (end_time - start_time)
average_time = total_time / iterations
return average_time

# Measure the time taken by example_function over 10 iterations

average_time = measure_time(example_function, iterations=10)
print(f"Average time: {average_time:.6f} seconds")

Explanation of the Example

 1. Define the Function:
o example_function is a placeholder for the code you want to measure.
2. Measure Time Function:
o measure_time runs example_function multiple times (10 iterations in this
case).
o For each iteration, it records the start and end times, calculates the duration, and
accumulates the total time.
3. Calculate Average Time:
o After completing all iterations, the average time is computed by dividing the total
time by the number of iterations.

By using iterations in this way, you can achieve a more reliable measurement of the function's
performance, making it easier to compare different algorithms or optimizations.