Search Algorithms

Linear Search

Given an array of n elements, find a specific element (x) in the array and return it’s position.

public class LinearSearch {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i; // Element found at index i
            }
        }
        return -1; // Element not found
    }
}

Binary Search

Binary search tackles the problem of locating a specific element within a sorted array by repeatedly dividing the search interval in half. The algorithm compares the target value with the middle element of the array and decides whether the target lies in the left or right half of the array. This process continues recursively until the target is found or the search interval becomes empty.

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (arr[mid] == target) {
                return mid; // Element found at index mid
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1; // Element not found
    }
}

Constraints:

1. Sorted Collection: The array or list must be sorted in ascending or descending order. Without sorting, the binary search algorithm won’t function correctly.
2. Random Access: Binary search requires the ability to access elements by index. It is efficient in arrays or data structures that allow direct access to elements based on index positions, such as arrays in Java.
3. Comparable Elements: The elements in the array should be comparable. In Java, this typically means that the elements must implement the Comparable interface or a custom comparator must be provided to the binary search algorithm for comparison.
4. Static Data Structure: Binary search works well with static or non-changing data structures. If the collection is frequently modified, binary search might not be the most efficient choice due to the requirement of a sorted structure after each modification.

Interpolation Search

The interpolation search algorithm is designed to efficiently locate a target value within a sorted array by making intelligent guesses about the target’s position based on the distribution of elements. It’s an enhancement over binary search, particularly useful when the data is uniformly distributed and has a range of values.

Key Factors:

1. Uniform Data Distribution: Interpolation search performs well when the data has a uniform distribution. It utilizes this characteristic to estimate the probable position of the target value.
2. Sorted Collection: Like binary search, interpolation search requires the array to be sorted either in ascending or descending order.

Advantage:

The main advantage of interpolation search over binary search lies in its ability to make more informed guesses about the target’s position. This is particularly useful when dealing with uniformly distributed data. In scenarios where the elements are evenly spaced out or have a specific distribution pattern, interpolation search can potentially reduce the number of iterations needed to find the target compared to binary search.

Limitation:

However, interpolation search might perform poorly if the data is not uniformly distributed or has irregular gaps between elements. In such cases, the estimates made by the interpolation formula might not be accurate, leading to suboptimal search performance.

public class InterpolationSearch {
    public static int interpolationSearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left <= right && target >= arr[left] && target <= arr[right]) {
            int pos = left + ((target - arr[left]) * (right - left)) / (arr[right] - arr[left]);

            if (arr[pos] == target) {
                return pos; // Element found at index pos
            } else if (arr[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        return -1; // Element not found
    }
}