searching

Binary Search:

int binarySearch(int arr[], int x) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // Check if x is present at mid 
            if (arr[m] == x) 
                return m; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    }


Jump Search:

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 8.
STEP 5: Perform linear search from index 8 to get the element 55

Works only 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 binary search is costly, we use Jump Search.


Exponential Search:

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)
 
Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite.
It works better than Binary Search for bounded arrays, and also when the element to be searched is closer to the first element.


Fibonacci Search:

Fibonacci Search divides given array in unequal parts
Binary Search uses division operator to divide range. Fibonacci Search doesn’t use /, but uses + and -. The division operator may be costly on some CPUs.
Fibonacci Search examines relatively closer elements in subsequent steps. So when input array is big that cannot fit in CPU cache or even in RAM, Fibonacci Search can be useful.

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.


Interpolation Search:

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. On the other hand, interpolation search may go to different locations according to the value of the key being searched. 
For example, if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.