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