Skip to content

Searching

Searching refers to the process of finding a specific element or value within a collection of data, such as arrays, lists, databases, or files. Efficient searching is crucial for performance in many applications, from databases to web search engines.

Why is Searching Important?

  • Data Retrieval: Quickly locate information in large datasets.
  • Optimization: Many algorithms rely on searching as a subroutine.
  • User Experience: Fast search improves usability in apps and websites.

Types of Searching

Linear search is the simplest searching algorithm. It checks each element in the collection sequentially until the target is found or the end is reached.

fun linearSearch(arr: IntArray, target: Int): Int {
    for (i in arr.indices) {
        if (arr[i] == target) return i
    }
    return -1
}

Pros: Simple, works on unsorted data.
Cons: Slow for large datasets (O(n) time).

Binary search is much faster but requires the data to be sorted. It repeatedly divides the search interval in half.

fun binarySearch(arr: IntArray, target: Int): Int {
    var left = 0
    var right = arr.size - 1
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
}

Pros: Fast (O(log n)), efficient for large sorted datasets.
Cons: Requires sorted data.

Interpolation search improves upon binary search for uniformly distributed data by estimating the position of the target.

Algorithm:

  • Estimate the position using the formula: pos = low + ((target - arr[low]) * (high - low) // (arr[high] - arr[low]))
  • Check if the estimated position matches the target.
  • Adjust search range accordingly.
fun interpolationSearch(arr: IntArray, target: Int): Int {
    var low = 0
    var high = arr.size - 1
    while (low <= high && arr[low] <= target && target <= arr[high]) {
        if (arr[low] == arr[high]) {
            return if (arr[low] == target) low else -1
        }
        val pos = low + ((target - arr[low]) * (high - low) / (arr[high] - arr[low]))
        if (arr[pos] == target) {
            return pos
        } else if (arr[pos] < target) {
            low = pos + 1
        } else {
            high = pos - 1
        }
    }
    return -1
}

Pros: Faster than binary search for uniformly distributed data.
Cons: Not suitable for non-uniform data.

Exponential search is useful for unbounded or infinite lists. It finds the range where the target may exist and then uses binary search.

Algorithm:

  • Find range by repeated doubling.
  • Apply binary search in the found range.
fun exponentialSearch(arr: IntArray, target: Int): Int {
    if (arr.isEmpty()) return -1
    if (arr[0] == target) return 0
    var i = 1
    while (i < arr.size && arr[i] <= target) {
        i *= 2
    }
    var left = i / 2
    var right = minOf(i, arr.size - 1)
    while (left <= right) {
        val mid = left + (right - left) / 2
        when {
            arr[mid] == target -> return mid
            arr[mid] < target -> left = mid + 1
            else -> right = mid - 1
        }
    }
    return -1
}

Comparison Table

Algorithm Time Complexity Space Complexity Sorted Data Required Best Use Case
Linear Search O(n) O(1) No Small/unsorted datasets
Binary Search O(log n) O(1) Yes Large/sorted datasets
Interpolation Search O(log log n) O(1) Yes (uniform) Uniformly distributed data
Exponential Search O(log n) O(1) Yes Unbounded/large datasets

Tips and Best Practices

  • Choose the right algorithm based on data size and distribution.
  • Always check if the data is sorted before using binary or interpolation search.
  • For frequent searches, consider indexing or using hash tables.
  • Profile and test performance for your specific use case.

Explore more searching problems and solutions in the problems section.