1 month, 2 weeks

Searching Algorithms





Searching algorithms are used to find a specified element within a data structure. Numerous different searching algorithms exist, each of which is suited to a particular data structure of format of data. Different searching algorithms are used depending on each individual scenario. 
There are two simple searching algorithms:                               
      Sequential Search (linear Search)                                        
      Binary Search                                                                       

 

Linear Search


Pseudocode
   -Loop through the array starting at the first element until the value of target matches one of the array elements.
   -If a match is not found, return -1.

def search(arr, n, x):                                                         
      for i in range(0, n):                                                      
           if (arr[i] == x):                                                         
                return i                                                              
      return -1                                                                     

Time complexity: O(N)
Auxiliary Space: O(1)
Linear search is rarely used practically because other search algorithms such as the binary search algorithm and hash tables allow significantly faster searching compared to Linear search.

 

Binary Search


Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The idea of binary search is to use the information that the array is sorted and reduce the time complexity to O(Log n). 
Binary Search Algorithm can be implemented in the following two ways:
    Iterative Method                                                                                    
    Recursive Method                                                                                 
The recursive method follows the divide and conquer approach.
-Compare x with the middle element.
-If x matches with the middle element, we return the mid index.
-Else if x is greater than the mid element, then x can only lie in the right (greater) half subarray after the mid element. Then we apply the algorithm again for the right half.
-Else if x is smaller, the target x must lie in the left (lower) half. So we apply the algorithm for the left half.

#Iterative Method                                                                                                    

def binarySearch(v, key):                               
    lo = 0                                                          
    hi = len(v) - 1                                              
    
    while hi - lo > 1:                                         
         mid = (hi + lo) // 2                                 
         if v[mid] < key:                                      
             lo = mid + 1                                      
         else: 
             hi = mid                                            
    if v[lo] == key:                                           
        return lo                                                
    elif v[hi] == key:                                        
        return hi                                               
    else:                                                        
        return -1                                               

 

# Recursive Method                                                                                                                         
def binarySearch(arr, l, r, key):                      
    if r >= l:                                                      
        mid = (r + l) // 2                                     
        if arr[mid] == key:                                 
            return mid                                        
                                                                             
        elif arr[mid] > key:                                          
            return binarySearch(arr, l, mid-1, key)        
        else:                                                               
            return binarySearch(arr, mid + 1, r, key) 
    else:                                                                 
        return -1                                                      

Time Complexities
Best case complexity: O(1)                                                                                           
Average case complexity: O(log n)                                                                               
Worst case complexity: O(log n)                                                                                   
Space Complexity: The space complexity of the binary search is O(1).                        

 

Jump Search


Jump sort requires the input array to be sorted.First an element having value greater than the element being searched is found. After this linear search is performed in a backward direction. Worst case occurs when the value to be searched is in the last section of the array. So, in this case the number of jumps will be n/k. Worst case occurs when the element being searched is present just after the element that has been compared while making the last jump. So, in this case k-1 comparisons will have to be made.

import math                                                                             
def jump_search(arr,search):                                                   
    low = 0                                                                                
    interval = int(math.sqrt(len(arr)))                                           
    for i in range(0,len(arr),interval):                                          
        if arr[i] < search:                                                             
            low = i                                                                         
        elif arr[i] == search:                                                        
            return i                                                                     
        else:                                                                            
            break                                                                         
    c=low                                                                                    
    for j in arr[low:]:                                                                    
        if j == search:                                                                    
            return c                                                                         
        c += 1                                                                                
    return "Not found"                                                                         

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 the advantage that we traverse back only once (Binary Search may require up to O(Log n) jumps, consider a situation where the element to be searched is the smallest element or just bigger than the smallest). So, in a system where binary search is costly, we use Jump Search.

 

Fibonacci Search


The Fibonacci search technique is a method of searching a sorted array using a divide and conquer algorithm that narrows down possible locations with the aid of Fibonacci numbers.Since it divides the array into two parts, although not equal, its time complexity is O(logn).
F(n+1)=F(n)+F(n-1)
where F(i) is the ith number of the Fibonacci series where F(0) and F(1) are defined as 0 and 1 respectively.
The first few Fibonacci numbers are:
0,1,1,2,3,5,8,13....
F(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1


def fibonacci_search(lst, target):                                                      
    size = len(lst)                                                                               
    start = -1                                                                                      
    f0 = 0                                                                                          
    f1 = 1                                                                                         
    f2 = 1                                                                                         
    while(f2 < size):                                                                       
        f0 = f1                                                                                
        f1 = f2                                                                                  
        f2 = f1 + f0                                                                         
     
    while(f2 > 1):                                                                             
        index = min(start + f0, size - 1)                                           
        if lst[index] < target:                                                               
            f2 = f1                                                                                    
            f1 = f0                                                                                
            f0 = f2 - f1                                                                            
            start = index                                                                           
        elif lst[index] > target:                                                                       
            f2 = f0                                                                                         
            f1 = f1 - f0                                                                                   
            f0 = f2 - f1                                                                                     
        else:                                                                                                  
            return index                                                                                   
    if (f1) and (lst[size - 1] == target):                                                          
        return size - 1                                                                                   
    return None                                                                                         

Similarities with Binary Search:  
  -Works for sorted arrays                                                                                                 
  -A Divide and Conquer Algorithm.                                                                                  
  -Has Log n time complexity.                                                                                            


Differences with Binary Search: 
   -Fibonacci Search divides given array into unequal parts
   -Binary Search uses a division operator to divide range. Fibonacci Search doesn’t use /, but uses + and -. The division operator may be costly on some  CPUs.
   -Fibonacci Search examines relatively closer elements in subsequent steps. So when the input array is big that cannot fit in CPU cache or even in RAM,  Fibonacci Search can be useful.
When the speed of access depends on the location previously accessed, Fibonacci search is better compared to binary search as it performs well on those locations which have lower dispersion. 

 

Uniform Binary Search


Uniform Binary Search is an optimization of Binary Search algorithm when many searches are made on same array or many arrays of same size. The algorithm is very similar to Binary Search algorithm. The only difference is a lookup table is created for an array and the lookup table is used to modify the index of the pointer in the array which makes the search faster.The algorithm maintains an index and the index is modified using the lookup table.The time complexity of this approach is O(log(n)).


Exponential Search
An exponential search (also called doubling search or galloping search or Struzik search) is an algorithm, created by Jon Bentley and Andrew Chi-Chih Yao in 1976, for searching sorted, unbounded/infinite lists. 
It is named exponential search because it finds the range holding element by searching for the first exponent k for which element at index pow(2,k) is greater than the target. Although its name is exponential search, the time complexity of this algorithm is logarithmic. It is very useful when arrays are of infinite size and converges to a solution much faster than binary search. 

Exponential search involves two steps:  
    - Find range where element is present.
    - Do Binary Search in above found range.

def exponentialSearch(arr, n, x):                                                                              
    if arr[0] == x:                                                                                                         
        return 0                                                                                                              
   
    i = 1                                                                                                                           
    while i < n and arr[i] <= x:                                                                                         
        i = i * 2                                                                                                                   
    return binarySearch(arr, i // 2, min(i, n-1), x)                                                             

 

def binarySearch( arr, l, r, x):                                                             
    if r >= l:                                                                                                 
        mid = ( r + l ) // 2                                                                                  
        
        if arr[mid] == x:                                                                           
            return mid                                                                                    
        if arr[mid] > x:                                                                                
              return binarySearch(arr, l,mid - 1, x)                                              
        
        return binarySearch(arr, mid + 1, r, x)                                                   
    
    return -1                                                                                                        


In exponential search, we first find a range where the required elements should be present in the array.
Time Complexity : O(Log n)   
Exponential Binary Search is particularly useful for unbounded searches, where size of array is infinite.

 

Interpolation Searching 
The Interpolation Search is an improvement over Binary Search for instances, where the values in a sorted array are uniformly distributed. Interpolation constructs new data points within the range of a discrete set of known data points. 

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

def interpolation_search(ordered_list, term):                                                                
    size_of_list = len(ordered_list) - 1                                                                             

    index_of_first_element = 0                                                                                         
    index_of_last_element = size_of_list                                                                          

    while index_of_first_element <= index_of_last_element:                                                            
        mid_point = nearest_mid(ordered_list, index_of_first_element, index_of_last_element, term)

        if mid_point > index_of_last_element or mid_point < index_of_first_element:                          
            return None                                                                                                                           

        if ordered_list[mid_point] == term:                                                                                           
            return mid_point                                                                                                                  

        if term > ordered_list[mid_point]:                                                                                               
            index_of_first_element = mid_point + 1                                                                                      
        else:                                                                                                                                            
            index_of_last_element = mid_point - 1                                                                                   

    if index_of_first_element > index_of_last_element:                                                                            
        return None                                                                                                                                         

The average-case time complexity of the interpolation search is O(log(log n)), whereas the worst-case time complexity of the interpolation search algorithm is O(n). This shows that interpolation search is better than binary search and provides faster searching in most cases. Interpolation search has an auxiliary space complexity of O(1). So it qualifies as an in place algorithm.


Responses(0)