Exponential Search: Complete Search Algorithm Guide

Introduction and Core Concepts

Exponential search, also known as doubling search or galloping search, is an efficient searching algorithm designed for sorted arrays, particularly when the size of the array is unknown or effectively unbounded. Unlike binary search, which requires prior knowledge of the array's bounds, exponential search dynamically discovers a relevant search range before applying a binary search within that window. This two-phase approach makes it exceptionally powerful for specific problem domains where traditional searching techniques are either inefficient or inapplicable.

The core idea behind exponential search is elegantly simple: instead of immediately dividing the entire search space in half, the algorithm first probes the array at exponentially increasing indices (1, 2, 4, 8, 16, ...) until it finds an interval where the target element must lie. Once this bounding range is identified, it performs a standard binary search within that much smaller interval. This strategy is particularly advantageous when the target element is located near the beginning of the array, as it avoids the overhead of processing the entire data structure.

Exponential search matters for several critical reasons in modern computer science. First, it provides an optimal solution for searching in unbounded or infinite arrays, a scenario that arises in streaming data, lazy-loaded collections, and certain file system structures where the total number of elements is not known in advance. Second, it achieves a time complexity of O(log i) where 'i' is the position of the target element, which can be significantly faster than binary search's O(log n) when i is much smaller than n. This makes it a preferred choice for large datasets where locality of reference suggests the desired element is likely near the start. Understanding exponential search deepens a developer's toolkit for designing efficient, adaptive algorithms.

Why Exponential Search Was Invented

The algorithm was formalized to address a limitation of binary search: the requirement that both the lower and upper bounds be known. In theoretical computer science, the concept of an "unbounded search" problem highlights this gap. If you are given a sorted array of unknown size and you need to find an element, you cannot calculate the midpoint as (low + high) / 2 because 'high' is undefined. Exponential search solves this by growing the search window exponentially until it overshoots the target, thereby creating a well-defined upper bound.

This property also makes it valuable in situations where determining the size of the collection itself is an expensive operation. For example, counting the number of records in a massive distributed database or determining the length of a linked list that is sorted but not indexed could take O(n) time. Exponential search sidesteps this cost entirely by never needing to know n.

Prerequisites for Using Exponential Search

Like binary search, exponential search has a non-negotiable prerequisite: the input collection must be sorted in ascending or descending order. The algorithm relies on the sorted property to decide whether to double the range or to terminate the exponential phase and begin binary searching. If the array is unsorted, the result is unpredictable and incorrect.

Additionally, the data structure must support random access in O(1) time, such as an array or a Python list. It is not suitable for data structures like linked lists where accessing the element at index 2^k requires traversing from the head each time, which would negate its logarithmic advantage. The elements must also be comparable using a consistent ordering relation.

How It Works

Exponential search operates in two distinct, sequential phases: the range-finding phase and the binary search phase. The interplay between these two phases is what gives the algorithm its efficiency and adaptability. Understanding each phase in detail is key to implementing and analyzing the algorithm correctly.

In the first phase, the algorithm starts by checking the element at index 0. If it matches the target, the search terminates immediately. Otherwise, it checks the element at index 1, then 2, then 4, then 8, and so on, following the pattern index = 2^j for j = 0, 1, 2, ... At each step, it compares the element at the current index with the target value. If the element at the current index is smaller than the target (assuming ascending order), it means the target, if it exists, must be beyond this index, so the algorithm doubles the index and continues. This continues until it finds an index 'i' such that arr[i] is greater than or equal to the target, or until it goes out of bounds of the array.

Once the exponential phase terminates, we have established a definitive search interval. If the last checked index was 'i', then we know the target must lie within the range [i/2, min(i, n-1)], where n is the array size. This is because we already know the target is greater than all elements before i/2 and less than or equal to the element at i (or i is beyond the array end). The second phase then simply executes a standard iterative or recursive binary search within this bounded interval. Because the size of this interval is proportional to the position of the target, the binary search operates on a much smaller sub-array than the original.

The Exponential Probing Sequence

The choice of doubling (base 2) is conventional but not mandatory. The sequence 1, 2, 4, 8, ... ensures that the range grows very quickly, allowing the algorithm to cover large distances in few steps. To find an element at position i, it takes only O(log i) probes to find the bounding range. For instance, to reach index 1024, only 10 probes are needed. This logarithmic growth is what keeps the first phase efficient.

If the array is bounded and the exponential probe exceeds the array length, the algorithm gracefully handles this by capping the upper bound to n-1. This ensures no out-of-bounds access occurs while still preserving the correctness of the search interval for the subsequent binary search.

Intuition Behind the Efficiency

Consider a sorted array with 1,000,000 elements where the target is at index 15. A standard binary search would start by checking the middle element at index 500,000, then 250,000, and so on, taking roughly 20 comparisons. Exponential search, however, will check indices 1, 2, 4, 8, 16. At index 16, it finds that arr[16] > target, so it knows the target is between indices 8 and 16. It then binary searches this 8-element window, taking only about 3-4 more comparisons. The total is around 8-9 comparisons versus 20, a significant saving. This advantage diminishes as the target moves toward the end of the array, where its performance converges to that of binary search.

Implementation

Implementing exponential search in Python is straightforward, especially when leveraging a helper function for binary search. Below are several robust implementations covering iterative, recursive, and unbounded array scenarios. Note that all comparisons using < and > are escaped for HTML safety as < and >.

Iterative Exponential Search with Binary Search Helper

This is the most common and production-ready implementation. It first handles edge cases, then finds the range exponentially, and finally delegates to an iterative binary search.

# Iterative Exponential Search - Most Efficient Version
def binary_search(arr, left, right, target):
    """Helper function: Standard iterative binary search."""
    while left <= right:
        mid = left + (right - left) // 2
        # Check if target is present at mid
        if arr[mid] == target:
            return mid
        # If target greater, ignore left half
        elif arr[mid] < target:
            left = mid + 1
        # If target is smaller, ignore right half
        else:
            right = mid - 1
    return -1

def exponential_search(arr, target):
    """Main exponential search function."""
    n = len(arr)
    # Handle edge cases
    if n == 0:
        return -1
    if arr[0] == target:
        return 0
    
    # Find range for binary search by repeated doubling
    i = 1
    while i < n and arr[i] <= target:
        # If target found at current power of 2, return
        if arr[i] == target:
            return i
        i = i * 2  # Double the index
    
    # Call binary search for the found range
    # Range is [i//2, min(i, n-1)]
    left = i // 2
    right = min(i, n - 1)
    return binary_search(arr, left, right, target)

# Example usage
arr = [2, 3, 4, 10, 40, 50, 80, 100, 120, 140, 160]
print(exponential_search(arr, 10))  # Output: 3
print(exponential_search(arr, 80))  # Output: 6

Recursive Implementation

For those who prefer a recursive style, the exponential phase can be implemented recursively, though the binary search helper is often kept iterative to avoid deep recursion stacks.

# Recursive Exponential Search
def binary_search_recursive(arr, left, right, target):
    """Recursive binary search helper."""
    if left > right:
        return -1
    mid = left + (right - left) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return binary_search_recursive(arr, left, mid - 1, target)
    else:
        return binary_search_recursive(arr, mid + 1, right, target)

def exponential_search_recursive(arr, target, i=1):
    """Recursive driver for exponential search."""
    n = len(arr)
    if n == 0:
        return -1
    if arr[0] == target:
        return 0
    # Base case for exponential phase: found range or out of bounds
    if i >= n or arr[i] >= target:
        left = i // 2
        right = min(i, n - 1)
        return binary_search_recursive(arr, left, right, target)
    # Recursive step: double the index
    return exponential_search_recursive(arr, target, i * 2)

Handling Unbounded or Infinite Arrays

This variant is crucial when the array size is unknown. In Python, we simulate an infinite array by catching an IndexError, which in a real system might be an I/O error or stream end signal. This version does not use len(arr).

# Exponential Search for Unbounded / Infinite Arrays
def exponential_search_unbounded(arr, target):
    """
    Search in a sorted array of unknown size.
    Simulates infinite array by handling out-of-bounds access.
    """
    if arr[0] == target:
        return 0
    
    # Find range without knowing n
    i = 1
    try:
        while arr[i] < target:
            i *= 2
            # In a true infinite array, arr[i] might raise exception
            # Here we just access it to trigger IndexError if out of bounds
            _ = arr[i] 
    except IndexError:
        # We have exceeded array bounds, so cap i
        pass
    
    # Now we have a range [i//2, i] but i may be out of bounds
    # We need to find the actual upper bound via binary search that handles bounds
    # For simplicity, we find n by capping
    # In practice, you would binary search with bound checks
    n = len(arr) # In real unbounded case, this is unknown
    # For demo, we find effective right bound
    left = i // 2
    right = min(i, n - 1) if 'n' in locals() else i
    
    # Use bounded binary search with exception handling
    while left <= right:
        mid = left + (right - left) // 2
        try:
            val = arr[mid]
        except IndexError:
            right = mid - 1
            continue
        if val == target:
            return mid
        elif val < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Finding First Occurrence (Lower Bound)

When duplicates exist, you may want the first occurrence. This requires a slight modification to the binary search phase to continue searching left even after finding the target.

# Exponential Search to Find First Occurrence
def binary_search_first_occurrence(arr, left, right, target):
    """Finds the first occurrence of target in range."""
    result = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continue searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return result

def exponential_search_first(arr, target):
    """Exponential search that returns first occurrence."""
    n = len(arr)
    if n == 0 or arr[0] > target:
        return -1
    if arr[0] == target:
        return 0
    i = 1
    while i < n and arr[i] < target:
        i *= 2
    # Even if arr[i] == target, we need to search left for first occurrence
    left = i // 2
    right = min(i, n - 1)
    return binary_search_first_occurrence(arr, left, right, target)

# Test with duplicates
arr_dup = [1, 2, 2, 2, 3, 4, 5, 6]
print(exponential_search_first(arr_dup, 2))  # Output: 1

Step-by-Step Example

Let us walk through a concrete, detailed example to solidify the mechanics. Consider the sorted array arr = [3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31] with n = 15. Our target is 15, which is at index 6.

We will trace both phases of the algorithm, showing the values of indices and comparisons at each step. This trace demonstrates why the algorithm is so efficient for elements not at the far end of the array.

Phase 1: Exponential Range Finding

We initialize i = 1. The algorithm checks if arr[0] == target. Here arr[0] = 3 which is not 15, so we enter the loop.

• Step 1: i = 1. Check arr[1] = 5. Since 5 < 15, target is beyond index 1. Double i: i = 2.
• Step 2: i = 2. Check arr[2] = 7. Since 7 < 15, continue. Double i: i = 4.
• Step 3: i = 4. Check arr[4] = 11. Since 11 < 15, continue. Double i: i = 8.
• Step 4: i = 8. Check arr[8] = 19. Since 19 > 15, we have found our upper bound! The loop terminates.

At termination, we know the target must be in the range [i/2, i] = [4, 8]. Specifically, the interval is [4, 8] because arr[4] = 11 < 15 and arr[8] = 19 > 15. The size of this interval is only 5 elements (indices 4,5,6,7,8), compared to the original 15.

Phase 2: Binary Search Within the Range

Now we perform a standard binary search on the sub-array arr[4...8] = [11, 13, 15, 17, 19] with left = 4 and right = 8.

• Binary Step 1: mid = 4 + (8 - 4) // 2 = 6. Check arr[6] = 15. This equals our target! The search returns index 6.

In this lucky case, the binary search found the target in just one comparison. In total, exponential search took 4 exponential probes + 1 binary probe = 5 comparisons. A standard binary search on the full array would have taken: mid=7 (17), then mid=3 (9), then mid=5 (13), then mid=6 (15) — also 4 comparisons. For this mid-array element, they are comparable. However, if the target had been 7 (index 2), exponential search would have taken 2 probes + 1 binary probe = 3 comparisons, while binary search would still take 3-4. The advantage becomes dramatic for large n.

Example Where Target is Absent

Suppose we search for 12 in the same array. Phase 1 proceeds identically and finds the range [4, 8] because arr[8]=19 > 12. Phase 2 binary search on [11, 13, 15, 17, 19]: mid=6 (15) > 12, so right=5; mid=4 (11) < 12, so left=5; mid=5 (13) > 12, so right=4; loop ends left > right, return -1. The algorithm correctly reports not found, and it did so without ever examining elements beyond index 8.

Complexity Analysis

Analyzing the complexity of exponential search requires understanding that its performance depends not on the total size n, but on the position i of the target element. This is a key distinction from binary search and is formalized using Big O notation.

The total time is the sum of the time for the exponential phase and the binary search phase. The exponential phase takes O(log i) steps to reach index i, because we double the index each time. The binary search phase operates on a range of size i - i/2 = i/2, which also takes O(log i) time. Therefore, the overall time complexity is O(log i). In the worst case where the target is at the end or not present, i approaches n, so the complexity becomes O(log n), identical to binary search.

Space complexity is minimal. The iterative implementation uses only a few variables (i, left, right, mid) and thus requires O(1) auxiliary space. A recursive implementation would use O(log i) stack space due to recursion depth, but this is generally avoided in favor of the iterative version for production code.

Detailed Breakdown of Cases

The best case occurs when the target is at index 0, requiring only a single comparison for O(1) time. The average case, assuming uniformly distributed targets, is still O(log n) but with a smaller constant factor than binary search if the distribution is skewed toward the front. The worst case is O(log n) when the element is at the end or absent, requiring the algorithm to double all the way to n and then binary search the last interval.

It is important to note that exponential search is not always strictly better than binary search. If the target is near the end of a very large array, exponential search will do slightly more work than binary search because it spends O(log n) steps just to find the range before even starting the binary search. However, it is never asymptotically worse.

Comparison of Constants

While Big O notation hides constant factors, they matter in practice. Exponential search performs about 2*log(i) comparisons in the worst case within its range (log i for doubling + log i for binary search). Binary search performs log n comparisons. When i << n, 2*log i < log n, making exponential search faster. The crossover point is roughly when i < sqrt(n). For example, if n = 1,000,000 (log2 n ≈ 20), exponential search is faster when i < 1024 (log2 i < 10, so 2*log i < 20).

Variations and Optimizations

The classic doubling strategy can be tuned and extended in several ways to better suit specific data distributions or system constraints. These variations often involve changing the growth factor or combining exponential search with other search techniques.

One common optimization is to use a different growth factor. Instead of doubling (multiplying by 2), one could triple (multiplying by 3) or use a factor of 1.5. A larger factor reaches the target range faster but creates a larger interval for the binary search phase. A smaller factor creates a tighter interval but takes more steps to get there. The optimal factor depends on the expected position of the target. For unbounded searches where the cost of probing is high, a larger factor may be preferable.

Another powerful variation is to replace the final binary search with another search algorithm better suited to the data. For instance, if the data is known to be uniformly distributed, using interpolation search instead of binary search in the second phase can yield O(log log i) average time, which is even faster. Similarly, if the range is very small, a simple linear scan might be more cache-friendly and faster due to lower overhead than binary search's branching.

Fractional Cascading and Galloping

In the context of merging multiple sorted lists, the term "galloping search" is often used interchangeably with exponential search. The idea is to gallop ahead exponentially to find the insertion point. This is used in Python's own Timsort algorithm, which is the default sorting algorithm for Python and Java. Timsort uses galloping mode to merge runs efficiently when one run consistently wins, switching from linear to exponential probing to find the next merge point quickly. This is a highly optimized, real-world application of the core idea.

Bounded Exponential Search

For arrays where n is known but large, a bounded version can prevent overshooting by a huge margin. Instead of doubling until arr[i] >= target, it doubles until i >= n or arr[i] >= target. This is the standard implementation shown earlier and is an optimization over the pure unbounded version that would otherwise try to access indices far beyond n.

Hybrid with Jump Search

Some implementations use an exponential phase to find a coarse range, then use jump search (with fixed step size sqrt(m) where m is range size) instead of binary search. This can be beneficial when backward jumps (as in binary search) are expensive, such as when searching on magnetic tape or in certain linked structures where seeking backwards has a cost. However, for RAM-based arrays, binary search remains superior for the second phase.

Real-World Applications

While binary search is more widely taught, exponential search shines in several niche but critically important real-world systems where its unique properties provide a decisive advantage. Its ability to handle unknown bounds and its efficiency for early-positioned elements make it indispensable.

In web servers and databases, exponential search is used for searching in log files and time-series data. Server logs are typically append-only and sorted by timestamp. When searching for a log entry from a recent time (which will be near the end if sorted ascending, or near the beginning if the log is viewed in reverse chronological order), exponential search can locate the relevant time window quickly without knowing the total log size, which may be terabytes and constantly growing.

In computer networks, exponential search is conceptually related to exponential backoff algorithms, though not identical. More directly, it is used in searching for available network resources or in routing tables where the table size may not be known to the searching node. It is also used in the implementation of unbounded binary search for finding the first occurrence of a condition in an infinite sequence, such as finding the first bad version in a software release history where versions are generated on the fly.

Specific System Examples

One of the most prominent examples is in searching unbounded arrays or streams. For instance, the Java `Arrays` utility and C++ STL do not directly provide exponential search, but many custom implementations for searching in files of unknown size use it. If you have a large sorted file on disk and you memory-map it, you may not want to stat the file to get its size first; you can just exponentially probe until you hit EOF.

Another application is in finding the range of a target value to count occurrences. By using exponential search to find the first and last occurrence of a value, you can count duplicates in O(log i) time. This is useful in databases for cardinality estimation.

When NOT to Use Exponential Search

Despite its strengths, exponential search is not a universal replacement for binary search. If the array size is known and small, or if the target is equally likely to be anywhere in the array (uniform distribution), the overhead of the exponential phase makes it slightly slower on average than a direct binary search. In such cases, the simplicity and slightly better worst-case constant of binary search make it the better choice. Also, if the array is not sorted or does not support random access, neither algorithm is appropriate.

Comparison with Alternatives

Choosing the right search algorithm depends on the characteristics of your data and the constraints of your system. Exponential search occupies a unique niche, but it is essential to understand how it compares to other common searching techniques to make an informed decision.

Binary search is the gold standard for searching in a known, sorted, random-access array. It has guaranteed O(log n) time and is very simple to implement. Linear search is the baseline, requiring no sorting but taking O(n) time, making it only suitable for small or unsorted data. Interpolation search improves on binary search for uniformly distributed data by guessing the position based on value, achieving O(log log n) average time but degrading to O(n) in the worst case. Jump search is another alternative that jumps ahead by fixed steps (sqrt(n)) and then does a linear scan, achieving O(sqrt(n)) time, which is worse than logarithmic but has fewer backward jumps.

Exponential search distinguishes itself by its O(log i) complexity, where i is the target's index. This makes it strictly better than binary search when i is small, and never worse asymptotically. Its other major advantage is handling unbounded arrays, a feat none of the other logarithmic algorithms can claim without modification.

Decision Framework

To choose an algorithm, ask these questions: Is the array sorted? If no, use linear search or sort first. Is the size known? If no, exponential search is the clear winner. Is the target likely to be near the start? If yes, exponential search will be faster. Is the data uniformly distributed and very large? Consider interpolation search. For most general cases with known size, binary search remains the default due to its simplicity and predictable performance. Exponential search is the specialist tool for the unbounded or front-biased case.

Common Mistakes and Best Practices

Even though the algorithm is conceptually simple, several subtle pitfalls can lead to bugs, out-of-bounds errors, or performance degradation. Adhering to best practices ensures a correct and efficient implementation.

A frequent mistake is forgetting to handle the edge case where the target is at index 0. The exponential loop starts at i=1, so if arr[0] is the target, the loop condition arr[i] <= target might incorrectly skip it or the binary search range [i/2, i] might not include it. Always check arr[0] explicitly before entering the exponential phase. Another common error is integer overflow when doubling i, especially in languages like Java or C++ where integers have fixed size. In Python this is not an issue due to arbitrary-precision integers, but in other languages, one should check if i > n/2 before doubling to prevent overflow.

Off-by-one errors in defining the binary search range are also prevalent. The correct range after the loop terminates is [i//2, min(i, n-1)], not [i, 2*i] or [0, i]. Remember that the loop stops when arr[i] >= target, so the target must be between the previous power of two and the current one. Using i//2 as the left bound is crucial for correctness and for maintaining the O(log i) bound. Using 0 as the left bound would degrade the algorithm to O(log n) and lose its advantage.

Best Practices for Robust Code

Always validate inputs: check for an empty array and for None values. Use an iterative binary search helper to avoid recursion depth issues and to keep space complexity at O(1). When implementing for an unbounded array, ensure all array accesses are wrapped in bounds checking or exception handling to avoid crashes. Write comprehensive tests that cover targets at the beginning, middle, end, not present, array with one element, and array with duplicates.

For performance, avoid recalculating len(arr) inside the loop. Cache it in a variable n. Also, prefer the iterative doubling loop over recursion for the exponential phase, as it is more efficient and avoids function call overhead. If you are searching for the same array multiple times, consider whether the target distribution justifies exponential search; if searches are uniformly random, a plain binary search might have a better average constant factor.

Pitfall: Using Exponential Search on the Wrong Data Structure

A subtle but critical mistake is applying exponential search to a linked list or other sequential-access structure. The analysis assumes O(1) random access. On a linked list, accessing arr[i] takes O(i) time, so the exponential phase which accesses indices 1, 2, 4, 8... would actually take O(1 + 2 + 4 + 8 + ... + i) = O(i) time, which is linear and destroys the logarithmic advantage. Always ensure your data structure is an array, list, or other random-access container before choosing this algorithm.

Interview Questions

Exponential search is a favorite topic in technical interviews because it tests understanding of binary search, complexity analysis, and handling of edge cases like unbounded arrays. Here are common questions and how to approach them.

Question 1: Search in a Sorted Array of Unknown Size

Problem: You are given a sorted array of unknown size (you cannot call len() or size()). You have an API `get(index)` that returns the element at that index or raises an exception if out of bounds. Find the index of a target element or return -1 if not found.

Approach: This is the textbook use case for exponential search. Explain that you will first find the bounds exponentially: start at index 1 and double until `get(i)` raises an exception or returns a value >= target. Then you have a bounded range [i/2, i] where you can perform a binary search that handles out-of-bounds by treating it as infinity. Discuss time complexity O(log i) and space O(1). Be sure to mention handling the case where the array is empty or target is at index 0.

Question 2: What is the Time Complexity of Exponential Search and When is it Better than Binary Search?

Problem: Analyze the time complexity of exponential search and explain under what conditions it outperforms binary search.

Approach: State that the complexity is O(log i) where i is the index of the target, which is O(log n) in the worst case. It outperforms binary search when the target is near the beginning of the array, specifically when i < n/2 and more precisely when i < sqrt(n) if considering constant factors (2*log i < log n). Provide an example: for n=1,000,000, if target is at index 10, exponential search takes ~8 comparisons vs ~20 for binary search. Mention it is never asymptotically worse than binary search but can be slightly slower by a constant factor when the target is at the end.

Question 3: Find the First and Last Occurrence Using Exponential Search

Problem: Given a sorted array with duplicates, how would you find the first and last occurrence of a target value efficiently?

Approach: Explain you can use exponential search to find any occurrence, but to find the boundaries, you need to modify the binary search phase. For the first occurrence, after finding the range [i/2, i], perform a binary search that continues searching left even after finding the target (as shown in the implementation section). For the last occurrence, continue searching right. Alternatively, you can find the first occurrence of target and the first occurrence of target+1, then derive the count. Complexity remains O(log i).

Question 4: Implement Exponential Search Without Using len()

Problem: Write code for exponential search without using the length of the array. Discuss how you handle out-of-bounds access.

Approach: Walk through the code for the unbounded case. Show the try/except block for Python or bounds-checking logic. Emphasize the two phases: exponential probing with exception handling to find the upper bound, followed by a binary search that also handles out-of-bounds by adjusting the right pointer. This tests practical coding skills and understanding of the algorithm's core strength.

Question 5: Compare Exponential Search with Jump Search and Interpolation Search

Problem: How does exponential search differ from jump search and interpolation search? When would you choose one over the other?

Approach: Create a mental comparison table. Highlight that exponential search has O(log i) vs jump search O(√n) vs interpolation O(log log n) average but O(n) worst. Exponential is best for unbounded arrays and front-biased targets, interpolation is best for large uniformly distributed arrays, and jump search is best when backward jumps are expensive. Mention prerequisites: all require sorted arrays, but only exponential handles unknown size. This demonstrates breadth of knowledge in searching algorithms.