WikiGalaxy
Introduction to Searching Algorithms
Linear Search:
Linear Search is the simplest searching algorithm. It checks every element in the list until it finds the target value or reaches the end of the list.
int linearSearch(int[] arr, int target) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
This algorithm has a time complexity of O(n) because it may need to check each element.
Binary Search
Binary Search:
Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the portion of the list that could contain the item in half until you've narrowed down the possible locations to just one.
int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
The time complexity of Binary Search is O(log n), which makes it much faster than Linear Search for large lists.
Jump Search
Jump Search:
Jump Search is a searching algorithm for sorted arrays. The basic idea is to check fewer elements by jumping ahead by fixed steps or skipping some elements in place of searching all elements.
int jumpSearch(int[] arr, int target) {
int n = arr.length;
int step = (int)Math.floor(Math.sqrt(n));
int prev = 0;
while (arr[Math.min(step, n)-1] < target) {
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n) return -1;
}
while (arr[prev] < target) {
prev++;
if (prev == Math.min(step, n)) return -1;
}
if (arr[prev] == target) return prev;
return -1;
}
Jump Search has a time complexity of O(√n), which is better than Linear Search but not as good as Binary Search.
Interpolation Search
Interpolation Search:
Interpolation Search is an improved variant of Binary Search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.
int interpolationSearch(int[] arr, int target) {
int low = 0, high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low == high) {
if (arr[low] == target) return low;
return -1;
}
int pos = low + (((high - low) / (arr[high] - arr[low])) * (target - arr[low]));
if (arr[pos] == target) return pos;
if (arr[pos] < target) low = pos + 1;
else high = pos - 1;
}
return -1;
}
The time complexity of Interpolation Search is O(log log n) when the elements are uniformly distributed, making it faster than Binary Search in such cases.
Exponential Search
Exponential Search:
Exponential Search involves two steps. First, find the range where the element is present. Second, perform a Binary Search within that range. This algorithm is particularly useful for unbounded or infinite lists.
int exponentialSearch(int[] arr, int target) {
if (arr[0] == target) return 0;
int i = 1;
while (i < arr.length && arr[i] <= target) i = i * 2;
return binarySearch(arr, target, i / 2, Math.min(i, arr.length - 1));
}
int binarySearch(int[] arr, int target, int left, int right) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}
The time complexity for Exponential Search is O(log n), and it is particularly efficient for large lists.
