Let Us Understand Searching Algorithms

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- The 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 the target is found & ‘Failure’ when the target is not found.

These algorithms are mainly classified into 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 types of search algorithms are more efficient than the 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 a 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 search algorithms in detail 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 algorithm 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 the 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 the 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 shortlists.

A linear search algorithm is considered the most basic of all search algorithms. The binary search method is considered the best searching algorithm.

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 concerning 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 a 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 the 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 the above algorithm is O(n).

Binary Search

This type of searching algorithm is used to find the position of a specific value contained in a sorted array. The binary search algorithm works on the principle of divide & conquer and it is considered the best searching algorithm because of its faster speed to search ( Provided the data is in sorted form).

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, the search needs to go higher, if not, then it needs to look at the descending portion of the array.

A binary Search Tree is a node-based binary tree data structure that 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 a more clear understanding of 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). The 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 a 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 searched is the smallest element or smaller than the smallest). So in a system 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 algorithm, 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 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. 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 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]
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
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.

Below is the implementation of the 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 4

Time Complexity: If elements are uniformly distributed, then O (log log n)). In the worst case, it can take up to 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 in 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

The exponential search involves 2 basic steps:

1. Find the range where the element is present
2. Do Binary Search in the above-found range.

How to find the range where elements 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 the last element of a subarray is not greater.

Once we find an index I (after a 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 the previous iteration)

Given below are the implementations of the 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 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 the size of the 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 the 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 FOUND

Algorithm:
1- Take the first node of the second list.
2- Start matching the first list from this first node.
3- If whole lists match return true.
4- Else break and take the first list to the first node again.
5- And take the second list to its second node.
6- Repeat these steps until any of the linked lists becomes empty.
7- If the first list becomes empty then the list is found else not.

Fibonacci Search

The 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 the 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 a given array into unequal parts
2. Binary Search uses a division operator to divide the 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 the 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) &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 the given array. Let the found Fibonacci number be fib (m’th Fibonacci number). We use (m-2)’the Fibonacci number as the index (If it is a valid index).

Let (m-2)’the 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 is 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:
3. Compare x with the last element of the range covered by fibMm2
4. If x matches, return index
5. Else If x is less than the element, move the three Fibonacci variables two Fibonacci down, indicating elimination of approximately rear two-thirds of the remaining array.
6. 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.

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.

The 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).

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 the least number of comparisons. (Do you think binary search is optimal to search a key in a sorted array?)

Without much theory, here is a 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 the worst case. If we observe, we are using two comparisons per iteration except during the final successful match, if any. In practice, the comparison would be a costly operation, it won’t be just a primitive type of comparison. It is more economical to minimize comparisons than that theoretical limit.

See the below figure on initializing indices in the next implementation.

The following implementation uses fewer 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 points as two different consecutive elements. We need one more comparison to trace search status.

Problem Statement: Given an array of N distinct integers, find the floor value of the 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 the floor value of the key. We keep moving the left pointer to right most as long as the invariant holds. Eventually left pointer points to an element less than or equal to the key (by definition floor value). The following are possible corner cases,

—> If all elements in the array are smaller than the key, the left pointer moves till the last element.

—> If all elements in the array are greater than the 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 several occurrences of input ‘key’ in log N time.

The idea here is to find left and right occurrences of keys in the array using binary search. We can modify the floor function to trace the rightmost occurrence and the left-most occurrence. Here is the 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 the minimum element in the array.

We can see a pictorial representation of the sample input array in the below figure.

We converge the search space till l and r point to a 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.

In A Nutshell...

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 if 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!

FAQ's