Learning Searching Algorithms

Linear Search – O(n)

Go through the entire array and check if the element exists

static int LinearSearch(int arr[], int x) { 
    int n = arr.length;
    for (int i = 0; i < n; i++) { 
        if (arr[i] == x) {
            return i; 
        } 
    }
    return -1; // If value is not found 
} 

Binary Search – O(n log(n))

• Compare x with the middle element.
• If x matches with middle element, we return the mid index.
• If x is greater than the mid element, then do a Binary Search for right half.
• If x is left is lower, then do a Binary Search for left half.

//Recursive
int binarySearch(int arr[], int left, int right, int x) { 
    if (right>=left) { 
        int mid = left + (right - left)/2; 
        if (arr[mid] == x) {
           return mid; 
        }
        if (arr[mid] > x) {
           return binarySearch(arr, left, mid-1, x); 
        } else {
            return binarySearch(arr, mid+1, right, x); 
        }
    } 
    return -1; 
} 

//Non Recursive
int binarySearch(int arr[], int x) { 
    int left = 0, right= arr.length - 1; 
    while (left<= r) { 
        int mid = left + (right - left)/2; 
        if (arr[mid] == x) {
            return mid; 
        }
        if (arr[mid] < x) {
            left = mid + 1; 
        } else {
            right = mid - 1; 
        }
    } 
    return -1; 
}

// Array =[2, 3, 4, 10, 40, 50, 60, 70, 80, 90]
// Mid = 4 Left = 0 Right = 9
// Mid = 7 Left = 5 Right = 9
// Mid = 8 Left = 8 Right = 9
// Element found at index 8

ExponentialSearch – O(log(n))

• Find the range where element is present
• Do Binary Search in above found range.

static int exponentialSearch(int arr[], int n, int x) { 
    if (arr[0] == x) 
        return 0; 
    // Find range for binary search by 
    // repeated doubling 
    int i = 1; 
    for (;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); 
    // binarySearch(Array,fromIndex,toIndex,keyToFind)
} 

JumpSearch – √(n)

• Loop, jump and add the step to i
  
• linearly traverse the array till the array element is less the required element 
• and the previous element index is less than i

public static int jump_search(int[] arr, int x) { 
    int n = arr.length; 
    int step = (int) Math.floor(Math.sqrt(n)); 
    int prev = 0, i = 0;
    
    for (; i < n && arr[i] < x; prev = i, i += step);
    
    if (i >= n) return -1;
    
    for (++prev; arr[prev] < x && prev < i; ++prev);

    return (arr[prev] == x) ? prev : -1; 
} 

InterpolationSearch – O(n)

• The Interpolation Search is an improvement over Binary Search
• interpolation search may go to different locations according to the value of the key being searched
• if the value of the key is closer to the last element, interpolation search is likely to start search toward the end side.

static int interpolationSearch1(int arr[],int x) {
  int low = 0, high = (arr.length - 1),pos; 
  
  for (;low <= high && x >= arr[low] && x <= arr[high];) {
     pos = low + (((high-low) / (arr[high]-arr[low]))*(x - arr[low]));
     
     if (arr[pos]==x) {
        return pos;
     }else if (arr[pos]<x) {
        low=pos+1;
     }else {
        high=low-1;
     }
  }
  return -1;
}