Let Us Understand Searching Algorithms – is an article many of you are most interested in today !! Today, let’s InApps.net learn Let Us Understand Searching Algorithms – in today’s post!
When searching for data, the difference between a fast application and a slower one lies in the accurate use of a search algorithm. Searching algorithms is a basic, fundamental step in computing done via a step-by-step method to locate specific data among a collection of data.
All search algorithms make use of a search key to complete the procedure. And they are expected to return a success or a failure status ( in boolean true or false value).
In computer science, there are various types of search algorithms available and the way they are used decides the performance and efficiency of the data available(how the data is being used).
What is a Search Algorithm?
According to Wikipedia- Search algorithm is-
Any algorithm which solves the search problem, namely, to retrieve information stored within some data structure, or calculated in the search space of a problem domain, either with discrete or continuous values.
Searching Algorithms are designed to check or retrieve an element from any data structure where it is being stored.
They search for a target (key) in the search space, like-
- All students in the class.
- All numbers in a given list.
These operations give one of the 2 possible outcomes- Success or Failure, i.e- ‘Success’ when target is found & ‘Failure’ when target is not found.
These algorithms are mainly classified in 2 categories according to their type of search operations. And they are-
- Sequential Search: In this, the list or array is traversed sequentially and every element is checked. For example: Linear Search
- Interval Search: These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are more efficient than Linear Search method, as they repeatedly target the center of the search structure and divide the search space in 2 half. For Example: Binary Search.
Types of Searching Algorithms
- Linear Search
- Binary Search
- Jump Search
- Interpolation Search
- Exponential Search
- Sublist Search (Search a linked list in another list)
- Fibonacci Search
- The Ubiquitous Binary Search
There are few more types of algorithms left to be discussed here, but all cannot be covered in one post, so we will cover those left outs in another topic.
Let us understand each one of these types of searching algorithms in details with examples & illustrations-
Linear Search
A linear search or sequential search is a method for finding an element within a list. This type of searching algorithms sequentially checks each element of the list until a match is found or the whole list has been searched.
A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list.
If each element is equally likely to be searched, then linear search has an average case of n+1/2 comparisons, but the average case can be affected if the search probabilities for each element vary.
Linear search is rarely practical because other search algorithms and schemes, such as the binary search algorithm and hash tables, allow significantly faster searching for all but short lists.
A linear search algorithm is considered the most basic of all search algorithms. Binary search method is considered as the best searching algorithms.
There are other search algorithms such as the depth-first search algorithm, breadth-first algorithm, etc.
The efficiency of a search algorithm is measured by the number of times a comparison of the search key is done in the worst case. The notation used in search algorithms is O(n), where n is the number of comparisons done.
It gives the idea of the asymptotic upper bound of execution time required for the algorithm with respect to a given condition.
Let us understand this with an example-
Problem: Given an array arr[] of n elements, write a function to search a given element x in arr[].
Examples-
Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 110;
Output : 6
Element x is present at index 6
Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 175;
Output : -1
Element x is not present in arr[].A simple approach is to do linear search, i.e
- Start from the leftmost element of arr[] and one by one compare x with each element of arr[]
- If x matches with an element, return the index.
- If x doesn’t match with any of elements, return -1.
Example of Linear Search in Java
// Java code for linearly searching x in arr[]. If x
// is present then return its location, otherwise
// return -1
class GFG
{
public static int search(int arr[], int x)
{
int n = arr.length;
for(int i = 0; i < n; i++)
{
if(arr[i] == x)
return i;
}
return -1;
}
public static void main(String args[])
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int result = search(arr, x);
if(result == -1)
System.out.print("Element is not present in array");
else
System.out.print("Element is present at index " + result);
}
}Example of Linear Search in Python3-
# Python3 code to linearly search x in arr[].
# If x is present then return its location,
# otherwise return -1
def search(arr, n, x):
for i in range (0, n):
if (arr[i] == x):
return i;
return -1;
# Driver Code
arr = [ 2, 3, 4, 10, 40 ];
x = 10;
n = len(arr);
result = search(arr, n, x)
if(result == -1):
print("Element is not present in array")
else:
print("Element is present at index", result);Example of Linear Search in PHP-
<?php
// PHP code for linearly search x in arr[].
// If x is present then return its location,
// otherwise return -1
function search($arr, $x)
{
$n = sizeof($arr);
for($i = 0; $i < $n; $i++)
{
if($arr[$i] == $x)
return $i;
}
return -1;
}
// Driver Code
$arr = array(2, 3, 4, 10, 40);
$x = 10;
$result = search($arr, $x);
if($result == -1)
echo "Element is not present in array";
else
echo "Element is present at index " ,
$result;
Output-
Element is present at index 3
The time complexity of above algorithm is O(n).
Binary Search
This type of searching algorithms is used to find the position of a specific value contained in a sorted array. Binary search algorithm works on the principle of divide & conquer and it is considered the best searching algorithms because of its faster speed to search ( Provided the data is in sorted form). Using a binary search, you are more likely to find an item than if you use a linear search.
A binary search is also known as a half-interval search or logarithmic search.
It starts by searching in the middle of the array and going down the first lower or upper half of the sequence. If the median value is lower than the target value, that means that the search needs to go higher, if not, then it needs to look on the descending portion of the array.
Binary Search Tree, is a node-based binary tree data structure which has the following properties:
- The left subtree of a node contains only nodes with keys lesser than the node’s key.
- The right subtree of a node contains only nodes with keys greater than the node’s key.
- The left and right subtree each must also be a binary search tree. There must be no duplicate nodes.
A binary search is a quick and efficient method of finding a specific target value from a set of ordered items. By starting in the middle of the sorted list, it can effectively cut the search space in half by determining whether to ascend or descend the list based on the median value compared to the target value.
For example, with a target value of 8 and a search space of 1 through 11:
- The median/middle value is found and the pointer is set there, which in this case is 6.
- The target of 8 is compared to 6. Since 6 is smaller than 8, the target must be in the higher half.
- The pointer is moved to the next value (7) and compared to the target. It is smaller, therefore the pointer moves to the next higher value.
- The pointer is now on 8. Comparing this to the target, it is an exact match, therefore the target has been found.
Using binary search, the target only had to be compared to 3 values. Compared to doing a linear search, it would have started from the very first value and moved up, needing to compare the target to eight values.
A binary search is possible only with an ordered set of data, if the data is randomly arranged, then a linear search would yield results.
Example of Binary Search in Java-
// Java implementation of recursive Binary Search
class BinarySearch {
// Returns index of x if it is present in arr[l..
// r], else return -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the 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
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not present
// in array
return -1;
}
// Driver method to test above
public static void main(String args[])
{
BinarySearch ob = new BinarySearch();
int arr[] = { 2, 3, 4, 10, 40 };
int n = arr.length;
int x = 10;
int result = ob.binarySearch(arr, 0, n - 1, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}Example of Binary Search in Python-
# Python Program for recursive binary search.
# Returns index of x in arr if present, else -1
def binarySearch (arr, l, r, x):
# Check base case
if r >= l:
mid = l + (r - l)/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, l, mid-1, x)
# Else the element can only be present
# in right subarray
else:
return binarySearch(arr, mid + 1, r, x)
else:
# Element is not present in the array
return -1
# Test array
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 % d" % result
else:
print "Element is not present in array"Examples of Binary Search in PHP-
<?php
// PHP program to implement
// recursive Binary Search
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r]
// is present, otherwise -1
function binarySearch($arr, $l, $r, $x)
{
if ($r >= $l)
{
$mid = ceil($l + ($r - $l) / 2);
// If the element is present
// at the middle itself
if ($arr[$mid] == $x)
return floor($mid);
// If element is smaller than
// mid, then it can only be
// present in left subarray
if ($arr[$mid] > $x)
return binarySearch($arr, $l,
$mid - 1, $x);
// Else the element can only
// be present in right subarray
return binarySearch($arr, $mid + 1,
$r, $x);
}
// We reach here when element
// is not present in array
return -1;
}
// Driver Code
$arr = array(2, 3, 4, 10, 40);
$n = count($arr);
$x = 10;
$result = binarySearch($arr, 0, $n - 1, $x);
if(($result == -1))
echo "Element is not present in array";
else
echo "Element is present at index ",
$result;
Output-
Element is present at index 3For more clear understanding on Linear & Binary search, watch this video below-
Jump Search
Just like Binary Search, Jump Search is one of the searching algorithms 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 block (to be jumped) size m. Then we search at 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.
Example-
Let’s consider the following array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). Length of the array is 16. 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 9.
STEP 5: Perform linear search from index 9 to get the element 55.
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.
Let us check out the implementation in Java-
// Java program to implement Jump Search.
public class JumpSearch
{
public static int jumpSearch(int[] arr, int x)
{
int n = arr.length;
// Finding block size to be jumped
int step = (int)Math.floor(Math.sqrt(n));
// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[Math.min(step, n)-1] < x)
{
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++;
// If we reached next block or end of
// array, element is not present.
if (prev == Math.min(step, n))
return -1;
}
// If element is found
if (arr[prev] == x)
return prev;
return -1;
}
// Driver program to test function
public static void main(String [ ] args)
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610};
int x = 55;
// Find the index of 'x' using Jump Search
int index = jumpSearch(arr, x);
// Print the index where 'x' is located
System.out.println("
Number " + x +
" is at index " + index);
}
}Implementation in Python3-
# 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)Implementation in PHP-
<?php
// PHP program to implement Jump Search
function jumpSearch($arr, $x, $n)
{
// Finding block size to be jumped
$step = sqrt($n);
// Finding the block where element is
// present (if it is present)
$prev = 0;
while ($arr[min($step, $n)-1] < $x)
{
$prev = $step;
$step += sqrt($n);
if ($prev >= $n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
while ($arr[$prev] < $x)
{
$prev++;
// 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[$prev] == $x)
return $prev;
return -1;
}
// Driver program to test function
$arr = array( 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610 );
$x = 55;
$n = sizeof($arr) / sizeof($arr[0]);
// Find the index of '$x' using Jump Search
$index = jumpSearch($arr, $x, $n);
// Print the index where '$x' is located
echo "Number ".$x." is at index " .$index;
return 0;
?>Output-
Number 55 is at index 10
Time Complexity : O(√n)
Auxiliary Space : O(1)
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 an 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 search is the smallest element or smaller than the smallest). So in a systems where jumping back is costly, we use Jump Search.
Interpolation Search
Interpolation search is an improved variant of binary search. This search algorithm works on the probing position of the required value. It was first described by W. W. Peterson in 1957.
For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.
Interpolation search is that type of searching algorithms, used for searching for a key in an array that has been ordered by numerical values assigned to the keys ( key values ).
Let us understand this with an example-
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 take 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. Binary Search always goes to the middle element to check.
Also, 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 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]
pos = lo + [ (x-arr[lo])*(hi-lo) / (arr[hi]-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[]Algorithm
Rest of the Interpolation algorithm is the same except 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.
Below is the implementation of algorithm.
Example of Java-
// Java program to implement interpolation search
class Test
{
// Array of items on which search will
// be conducted.
static int arr[] = new int[]{10, 12, 13, 16, 18, 19, 20, 21, 22, 23,
24, 33, 35, 42, 47};
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
static int interpolationSearch(int x)
{
// Find indexes of two corners
int lo = 0, hi = (arr.length - 1);
// Since array is sorted, an element present
// in array must be in range defined by corner
while (lo <= hi && x >= arr[lo] && x <= arr[hi])
{
if (lo == hi)
{
if (arr[lo] == x) return lo;
return -1;
}
// Probing the position with keeping
// uniform distribution in mind.
int 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 upper part
if (arr[pos] < x)
lo = pos + 1;
// If x is smaller, x is in the lower part
else
hi = pos - 1;
}
return -1;
}
// Driver method
public static void main(String[] args)
{
int x = 18; // Element to be searched
int index = interpolationSearch(x);
// If element was found
if (index != -1)
System.out.println("Element found at index " + index);
else
System.out.println("Element not found.");
}
}Implementation in Python-
# Python program to implement interpolation search
# If x is present in arr[0..n-1], then returns
# index of it, else returns -1
def interpolationSearch(arr, n, x):
# Find indexs of two corners
lo = 0
hi = (n - 1)
# Since array is sorted, an element present
# in array must be in range defined by corner
while lo <= hi and x >= arr[lo] and x <= arr[hi]:
if lo == hi:
if arr[lo] == x:
return lo;
return -1;
# Probing the position with keeping
# uniform distribution in mind.
pos = lo + int(((float(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 upper part
if arr[pos] < x:
lo = pos + 1;
# If x is smaller, x is in lower part
else:
hi = pos - 1;
return -1
# Driver Code
# Array of items oin which 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 index != -1:
print "Element found at index",index
else:
print "Element not found"Implementation in PHP-
<?php
// PHP program to implement interpolation search
// If x is present in arr[0..n-1], then returns
// index of it, else returns -1.
function interpolationSearch($arr, $x, $n)
{
// Find indexes of two corners
$l = 0; $h = $n - 1;
// Since array is sorted, an element present
// in array must be in range defined by corner
while ($l <= $h and $x >= $arr[$l] and
$x <= $arr[$h])
{
if ($l == $h)
{
if ($arr[$l] == $x) return $l;
return -1;
}
// Probing the position with keeping
// uniform distribution in mind.
$m = intval($l + (($x - $arr[$l]) * ($h - $l) /
($arr[$h] - $arr[$l])));
// Condition of target found
if ($arr[$m] == $x)
{
return $m;
}
// If x is larger, x is in upper part
elseif ($arr[$m] < $x)
{
$l = $m + 1;
}
// If x is smaller, x is in the lower part
else
{
$h = $m - 1;
}
}
return -1;
}
// Driver Code
// Array of items on which search
// will be conducted.
$arr = array(10, 12, 13, 16, 18, 19, 20, 21,
22, 23, 24, 33, 35, 42, 47);
$n = count($arr);
$x = 18; // Element to be searched
$index = interpolationSearch($arr, $x, $n);
// If element was found
if ($index != -1)
echo "Element found at index " . $index;
else
echo "Element not found.";Output-
Element found at index 4Time Complexity: If elements are uniformly distributed, then O (log log n)). In worst case it can take upto O(n).
Auxiliary Space: O(1)
Exponential Search
Exponential search is also known as doubling or galloping search. This mechanism is used to find the range where the search key may present.
If L and U are the upper and lower bound of the list, then L and U both are the power of 2. For the last section, the U is the last position of the list. For that reason, it is known as exponential.
After finding the specific range, it uses the binary search technique to find the exact location of the search key.
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 1Exponential search involves 2 basic steps:
- Find range where element is present
- 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 in Java, Python and PHP.
// Java program to find an element x in a
// sorted array using Exponential search.
import java.util.Arrays;
class GFG
{
// Returns position of first occurrence of
// x in array
static int exponentialSearch(int arr[],
int n, int x)
{
// If x is present at firt location itself
if (arr[0] == x)
return 0;
// Find range for binary search by
// repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i*2;
// Call binary search for the found range.
return Arrays.binarySearch(arr, i/2,
Math.min(i, n), x);
}
// Driver code
public static void main(String args[])
{
int arr[] = {2, 3, 4, 10, 40};
int x = 10;
int result = exponentialSearch(arr, arr.length, x);
System.out.println((result < 0) ?
"Element is not present in array" :
"Element is present at index " +
result);
}
} Python
# Python program to find an element x
# in a sorted array using Exponential Search
# A recurssive 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
# occurence 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), 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 thye array"
else:
print "Element is present at index %d" %(result)PHP-
<?php
// PHP program to find an element x in a
// sorted array using Exponential search.
// Returns position of first
// ocurrence of x in array
function exponentialSearch($arr, $n, $x)
{
// If x is present at
// first location itself
if ($arr[0] == $x)
return 0;
// Find range for binary search
// 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), $x);
}
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r] is
// present, otherwise -1
function 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 element is smaller
// than mid, then it
// can only be present
// n left subarray
if ($arr[$mid] > $x)
return binarySearch($arr, $l,
$mid - 1, $x);
// Else the element
// can only be present
// in right subarray
return binarySearch($arr, $mid + 1,
$r, $x);
}
// We reach here when
// element is not present
// in array
return -1;
}
// Driver code
$arr = array(2, 3, 4, 10, 40);
$n = count($arr);
$x = 10;
$result = exponentialSearch($arr, $n, $x);
if($result == -1)
echo "Element is not present in array";
else
echo "Element is present at index ",
$result;
Output-
Element is present at index 3Time 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:
- Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite.
- It works better than Binary Search for bounded arrays, and also when the element to be searched is closer to the first element.
Sublist Search
Sublist search is used to detect a presence of one list in another list. Suppose we have a single-node list (let’s say the first list), and we want to ensure that the list is present in another list (let’s say the second list), then we can perform the sublist search to find it.
Given two linked lists, the task is to check whether the first list is present in 2nd list or not.
Input : list1 = 10->20
list2 = 5->10->20
Output : LIST FOUND
Input : list1 = 1->2->3->4
list2 = 1->2->1->2->3->4
Output : LIST FOUND
Input : list1 = 1->2->3->4
list2 = 1->2->2->1->2->3
Output : LIST NOT FOUNDAlgorithm:
1- Take first node of second list.
2- Start matching the first list from this first node.
3- If whole lists match return true.
4- Else break and take first list to the first node again.
5- And take second list to its second node.
6- Repeat these steps until any of linked lists becomes empty.
7- If first list becomes empty then list found else not.
Fibonacci Search
Fibonacci search technique is a method of searching algorithms where a sorted array uses a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers.
Compared to binary search where the sorted array is divided into two equal-sized parts, one of which is examined further, Fibonacci search divides the array into two parts that have sizes that are consecutive Fibonacci numbers.
Let us understand this by example-
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.Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an element in a sorted array.
Similarities with Binary Search:
- Works for sorted arrays
- A Divide and Conquer Algorithm.
- Has Log n time complexity.
Differences with Binary Search:
- Fibonacci Search divides given array in unequal parts
- Binary Search uses division operator to divide range. Fibonacci Search doesn’t use /, but uses + and -. The division operator may be costly on some CPUs.
- Fibonacci Search examines relatively closer elements in subsequent steps. So when 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 Fibinacci 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 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 element to be searched be x.
- 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].
- While the array has elements to be inspected:
- Compare x with the last element of the range covered by fibMm2
- If x matches, return index
- 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.
- Else x is greater than the element, move the three Fibonacci variables one Fibonacci down. Reset offset to index. Together these indicate elimination of approximately front one-third of the remaining array.
Implementation in Java-
// Java program for Fibonacci Search
import java.util.*;
class Fibonacci
{
// Utility function to find minimum
// of two elements
public static int min(int x, int y)
{ return (x <= y)? x : y; }
/* Returns index of x if present, else returns -1 */ public static int fibMonaccianSearch(int arr[],
int x, int n)
{
/* Initialize fibonacci numbers */ int fibMMm2 = 0; // (m-2)'th Fibonacci No.
int fibMMm1 = 1; // (m-1)'th Fibonacci No.
int 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
int 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
int 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 greater than the value at index
fibMm2, cut the subarray after i+1 */ else if (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 == 1 && arr[offset+1] == x)
return offset+1;
/*element not found. return -1 */ return -1;
}
// driver code
public static void main(String[] args)
{
int arr[] = {10, 22, 35, 40, 45, 50,
80, 82, 85, 90, 100};
int n = 11;
int x = 85;
System.out.print ("Found at index: "+
fibMonaccianSearch(arr, x, n));
}
}Python3
# 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 greater 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[offset+1] == x):
return offset+1;
# element not found. return -1
return -1
# Driver Code
arr = [10, 22, 35, 40, 45, 50,
80, 82, 85, 90, 100]
n = len(arr)
x = 85
print("Found at index:",
fibMonaccianSearch(arr, x, n)Illustration:
Let us understand the algorithm with below example:
Illustration assumption: 1-based indexing. Target element x is 85. Length of array n = 11.
Smallest Fibonacci number greate 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 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).
Visual Description-
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:
The Ubiquitous Binary Search
Problem Statement: Given a sorted array of N distinct elements. Find a key in the array using 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.
// Returns location of key, or -1 if not found
int BinarySearch(int A[], int l, int r, int key)
{
int m;
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.
// Invariant: A[l] <= key and A[r] > key
// Boundary: |r - l| = 1
// Input: A[l .... r-1]
int BinarySearch(int A[], int l, int r, int key)
{
int m;
while( r - l > 1 )
{
m = l + (r-l)/2;
if( A[m] <= key )
l = m;
else
r = m;
}
if( A[l] == key )
return l;
else
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. We need one more comparison to trace search status.
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
This is the implementation-
// 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]
int Floor(int A[], int l, int r, int key)
{
int m;
while( r - l > 1 )
{
m = l + (r - l)/2;
if( A[m] <= key )
l = m;
else
r = m;
}
return A[l];
}
// Initial call
int Floor(int A[], int size, int 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
int GetRightPosition(int A[], int l, int r, int key)
{
int m;
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
int GetLeftPosition(int A[], int l, int r, int key)
{
int m;
while( r - l > 1 )
{
m = l + (r - l)/2;
if( A[m] >= key )
r = m;
else
l = m;
}
return r;
}
int CountOccurances(int A[], int size, int key)
{
// Observe boundary conditions
int left = GetLeftPosition(A, -1, size-1, key);
int right = GetRightPosition(A, 0, size, key);
// What if the element doesn't exists in the array?
// The checks helps to trace that element exists
return (A[left] == key && key == A[right])?
(right - left + 1) : 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.
We are always trying our best to share valuable, informative and useful posts for our readers. And we welcome your feedback about any incorrect information, or you want to share more information about searching algorithms.
You can comment in the comment section below and we make sure to reply as soon as possible!
Source: InApps.net
Let’s create the next big thing together!
Coming together is a beginning. Keeping together is progress. Working together is success.
