WikiGalaxy
Linear Search Algorithm
Introduction
Linear search is a simple algorithm that checks each element in a list sequentially until the desired element is found or the list ends. It is easy to implement and understand but inefficient for large datasets.
Complexity Analysis
The time complexity of linear search is O(n), where n is the number of elements in the list. The space complexity is O(1) as it requires no additional space.
public class LinearSearch {
public static int search(int[] arr, int x) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
public static void main(String args[]) {
int[] arr = {2, 3, 4, 10, 40};
int x = 10;
int result = search(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}
Console Output:
Element found at index 3
Binary Search Algorithm
Introduction
Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half, comparing the target value to the middle element of the interval.
Complexity Analysis
The time complexity of binary search is O(log n), making it much faster than linear search for large datasets. The space complexity is O(1).
public class BinarySearch {
public static int binarySearch(int[] arr, int x) {
int l = 0, r = arr.length - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
public static void main(String args[]) {
int[] arr = {2, 3, 4, 10, 40};
int x = 10;
int result = binarySearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}
Console Output:
Element found at index 3
Jump Search Algorithm
Introduction
Jump search is a searching algorithm that works on sorted arrays. It works by jumping ahead by fixed steps and then performing a linear search within the block where the target element is located.
Complexity Analysis
The time complexity of jump search is O(√n), which is more efficient than linear search but less efficient than binary search. The space complexity is O(1).
import java.util.*;
public class JumpSearch {
public static int jumpSearch(int[] arr, int x) {
int n = arr.length;
int step = (int)Math.floor(Math.sqrt(n));
int prev = 0;
while (arr[Math.min(step, n)-1] < x) {
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
while (arr[prev] < x) {
prev++;
if (prev == Math.min(step, n))
return -1;
}
if (arr[prev] == x)
return prev;
return -1;
}
public static void main(String args[]) {
int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int x = 6;
int result = jumpSearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}
Console Output:
Element found at index 6
Interpolation Search Algorithm
Introduction
Interpolation search is an improvement over binary search for instances where the values in a sorted array are uniformly distributed. It estimates the position of the target value using a formula.
Complexity Analysis
The average time complexity is O(log log n), but it can degrade to O(n) in the worst case. The space complexity remains O(1).
public class InterpolationSearch {
public static int interpolationSearch(int[] arr, int x) {
int lo = 0, hi = arr.length - 1;
while (lo <= hi && x >= arr[lo] && x <= arr[hi]) {
if (lo == hi) {
if (arr[lo] == x) return lo;
return -1;
}
int pos = lo + (((hi-lo) / (arr[hi]-arr[lo]))*(x - arr[lo]));
if (arr[pos] == x)
return pos;
if (arr[pos] < x)
lo = pos + 1;
else
hi = pos - 1;
}
return -1;
}
public static void main(String args[]) {
int[] arr = {10, 12, 13, 16, 18, 19, 20, 21, 22, 23, 24, 33, 35, 42, 47};
int x = 18;
int result = interpolationSearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}
Console Output:
Element found at index 4
Exponential Search Algorithm
Introduction
Exponential search is a combination of binary search and a method to find the range where the target element might reside. It first finds the range by repeated doubling and then performs a binary search within that range.
Complexity Analysis
The time complexity is O(log n) for both average and worst cases, making it efficient for large datasets. The space complexity is O(1).
public class ExponentialSearch {
public static int binarySearch(int[] arr, int l, int r, int x) {
if (r >= l) {
int mid = l + (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;
}
public static int exponentialSearch(int[] arr, int x) {
if (arr[0] == x)
return 0;
int i = 1;
while (i < arr.length && arr[i] <= x)
i = i * 2;
return binarySearch(arr, i / 2, Math.min(i, arr.length - 1), x);
}
public static void main(String args[]) {
int[] arr = {2, 3, 4, 10, 40};
int x = 10;
int result = exponentialSearch(arr, x);
if (result == -1)
System.out.println("Element not present");
else
System.out.println("Element found at index " + result);
}
}
Console Output:
Element found at index 3
