• Home
• >
• Tech News
• >
• Let Us Understand Searching Algorithms – 2022
March 22, 2022 by Phu Nguyen

Let Us Understand Searching Algorithms – 2022

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 !

You can find content about Let Us Understand Searching Algorithms – from the Wikipedia website

When searching for data, the difference between a fast application and a slower one lies in the accurate use of search algorithm. Searching algorithms is a basic, fundamental step in computing done via step-by-step method to locate a specific data among a collection of data.

All search algorithms make use of a search key in order 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 type of search algorithms available and the way they are used decides the performance and efficiency of the data available( the manner in which 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-

1. All students in the class.
2. 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-

1. Sequential Search: In this, the list or array is traversed sequentially and every element is checked. For example: Linear Search
2. 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:

1. The median/middle value is found and the pointer is set there, which in this case is 6.
2. The target of 8 is compared to 6. Since 6 is smaller than 8, the target must be in the higher half.
3. 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.
4. 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 3`

For 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.

Read More:   Update Dashboards Are a Waste of Time and Money

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
}
}``````

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:

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

Output-

``Element found at index 4``

Time 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 1``````

Exponential search involves 2 basic 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 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:
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 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.

Read More:   Update BlazingSQL: A GPU-Accelerated SQL Engine

Applications of Exponential Search:

1. Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite.
2. 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

Algorithm:
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:

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 in unequal parts
2. 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.
3. 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) &approx; (1/3)*F(n) and
F(n - 1) &approx; (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.

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.
3. 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;

}

// 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;

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.

Read More:   No Longer a Myth – InApps Technology 2022

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

List of Keywords users find our article on Google:

 php array length php print array typeorm php array size array length php php array search types of search algorithms what is nestjs php array has key php echo array dotenv npm nestjs development company search algorithms java sub*.php?middle= index3.php?go= index3.php?left= nestjs frontend types of searching algorithms wawa hot food menu php get array length get index of item in list python php length of array time complexity of binary search nestjs platform advantages of nestjs searcho php array keys asymptotic notation wiki searching algorithms php array key array search in php array size php php get last element of array php size of array print array php java search algorithms if x nestjs typeorm what is the output of the following code? int x = 0; if (x < 4) { x = x +1; } system.out.println(“x is ” + x); binary search time complexity sorted array to binary search tree nestjs structure nestjs requirements nestjs benefits fibonacci team find in array php typeorm find array search php php net array if in array php php find value in array typeorm not in condition php array key value php search array binary solutions wikipedia php if in array php get array keys spaceo php array get value by key get last element of array php php function return array array find php echo array php php if key in array type orm searching algorithms in java php get first 5 elements of array worst case execution time sqrt 18 python get index of element in list which of the following is true regarding lists in python? php if is array length array php find the average value of the function over the given interval php indexof array php array index int[] arr = {1, 2, 3, 4, 5, 6, 7}; for (int i = 1; i < arr.length; i += 2){ arr[i] = arr[i – 1]; } python array search get first element of array php sqrt(40) worst case time complexity posx drivers find index of element in list python python find index of item in list times tables print outs hi lo driver test php order array by value php get first element of array time complexity of binary search tree python int to binary python sub array how to check if array is sorted java comparex simple binary search program in python php get first key of array nestjs use cases nestjs framework nestjs backend find an item in an array you are given an array f loor[] of size n where f loor[i] contains thefloor number of friend i. design a polynomial time algorithm to catch asmany of your friends as possible and take them to the top floor by t = n. which type of algorithm is performed on the array arr by this code?double[] arr = //initial values set here int a = //initial value set herefor (int i = a; i < arr.length-1; i++) { arr[i] = arr[i + 1]; } “x11 hospitality” what is the output of the following? class gfg { public static void main(string[] args) { int[] arr = new int[2]; arr[0] = 10; arr[1] = 20; for(int i = 0; i <= arr.length; i++) system.out.println(arr[i]); } } n+1 problem wikipedia gfg java backend gfg must do must do gfg spaceo home fibonacci number gfg find the domain of the function. (enter your answer using intervalnotation.) r/step1 “binary tree” class gfg step n time asymptotic notation wikipedia math formula wikipedia auxiliary space vs space complexity php get array key by value pos-x best search algorithm php subarray by keys array keys php php find key in array get first 10 elements of array php typeorm count typeorm findone php if not in array search in array php hi low game flowchart and pseudocode php find in array pointer wikipedia sqrt n wawa subs linear recruitment php get all keys of array element 55 element55 java offshore find the smallest number by which arr game integrate 1 x get array keys php offshore wiki php last index of array php else if php get array value by key php return array php search array key by value typeorm find where index match array formula php check array for value failure wikipedia php array has value php find index of object in array array match in php wawa uniform index match duplicate values typeorm length find the value of x if nestjs typorm for array php linear search php in array key auxiliary space complexity nestjs profiler php array search for value sequential algorithm typeorm string length types of searching find value in list python nestjs examples php array find php echo array values python binary search tree sqrt(144) array lenght php php echo new line php is array sqrt 34 match index formula php subarray typeorm index find value in array python sqrt 144 144 in binary dotenv-flow find element in array python find the value of n how to get last element of array in php how to integrate (1-x^2)^1/2 int x^n len(list)-1 php array number of elements php compare time strings php ob get content php print contents of array print array in php python if element in list average case complexity binary tree implementation in java compare 2 array in php java subarray method nestjs typeorm testing php check if array php compare arrays find differences php sub array the searching operation in an array is done using wawa 377 array php find array by value php java check element in array nestjs crypto algorithm implementation in python java search list last array key php php array 0 php array in array with key php get length of array php last element of array range of sqrt x the middle value of an ordered array of numbers is the depth first search python find index of element in array php in searching index match array is array php list index out of range python for loop searching algorithms java count items in array php find the exact values of x and r. get array length php index match minimum value next smaller element php get last two elements of array python find item in array what is time complexity of binary search class test public static void main string args how to print array in php java array subarray php check array length php first element of array what is the time complexity to count the number of elements in the linkedlist? 35 binary number arrays binarysearch average case complexity of binary search gfg touch java binary search tree menu wawa subs php if function php search in string search code in java search x what is algorithm in java what is the value of x if while array php dfs time complexity improvement of recursive programs from a logic programming point of view nestjs get npm dotenv php get key from value python3 return arr def binary search lower bound binary tree in python find index of object in array php get array value from key php java list search nestjs example php binary search php print array values sequential ob x size of binary tree sublist python binary search tree java implementation compare 2 array php if hi=10 and ie=x-4 what is the value of x int[] java nestjs ecommerce php count items in array php in array python find key by value search binary tree python ui:repeat index worst case complexity of binary search average case time complexity of binary search how to print binary tree in c java dotenv java search array php if array return array java binary search in linked list binary search tree python binary search tree time complexity depth of binary search tree index match an array what is log n array index php elif in php how to echo array in php length of array php length of binary tree php array count recursive python boolean indexing python find element in list binary search python get index of element in list python golang binary search tree is 1/x continuous java method return array list app with sublists nestjs example project python search in list static function php typeorm one to many algorithm and logic best case complexity binary index tree binary search complexity difference between o(n) and o(1) implementation of algorithms nestjs fundamentals php order array by key program for binary search in java python list time complexity python orderedset system.collections.sortedlist binary search upper bound breadth first search python formula index match python binary search implementation range function in php recursive binary search python what is linear search √55 php length array what is searching asymptotic bound nestjs advantages who uses nestjs algorithms algorithm efficiency subtrees
Rate this post

Let’s create the next big thing together!

Coming together is a beginning. Keeping together is progress. Working together is success.

Let’s talk

Recommended

September 23, 2023 by Julie Nguyen

A Detailed Guide to Outsourcing Mobile App Development Successfully in 2023 (Part I)

September 19, 2023 by Thuận Cao

What Is Business Process Outsourcing and How Does It Work?

September 6, 2023 by Julie Nguyen

Insourcing vs Outsourcing: Finding the Right Balance for Your IT Projects

September 6, 2023 by Julie Nguyen

Onshore vs Offshore Outsourcing: An In-depth Comparison for Newbie 2023

September 6, 2023 by Julie Nguyen

Rapid Application Development and Everything You Need to Know

August 28, 2023 by Julie Nguyen

Top 7 Must-know Outsourcing Mistakes and How to Avoid

August 11, 2023 by Julie Nguyen

Popular Outsourcing Models Compared – How to Choose the Best One in 2023?

August 6, 2023 by Julie Nguyen

Diving into ODC vs IT Staff Augmentation: 11 Key Distinctions Unveiled

June 17, 2023 by Phu Nguyen

Why Hire Offshore Developers for Your Startup is a Smart Move in 2023?

June 15, 2023 by Phu Nguyen

INAPPS TECHNOLOGY and AGORIZE: Partnership Announcement

Get a custom Proposal

`Success. Downloading...`