Linear Search, Binary Search, Hashing and Beyond: Pattern Based Searching

Given a list of integers, we need to find an element within it. We could rely on luck by randomly selecting an element with each attempt. The target element might be found on the first try, the second try, or after numerous attempts — potentially even requiring more tries M than the elements in the list N. While it’s true that with a small number of elements, probability theory suggests a reasonable chance of success, this method is not practical for our purposes. Therefore, we will neither rely on nor delve into Random Search in this discussion. Our intuition would naturally lead us to ask: “Is the list of integers sorted, or is it unsorted?” Based on the answer, we can choose between the following two options.

1. Linear Search
2. Binary Search

Linear Search:

If the list is unsorted, we would have to use linear search to find an element. In best case scenario, our first element would be the element we are looking for (which is very unlikely to happen every time) and we would have a time complexity of O(1).

However, in the worst-case scenario, where the target element is the last element or not present at all, the time complexity is O(n), where n is the number of elements in the list. Hence the upper bound for linear search is O(n).

To refresh your memory on a typical linear search, a code snippet in Python language is provided below:

def linear_search(lst, value):
    for index, item in enumerate(lst):
        if item == value:
            return index
    return -1

Binary Search:

Miracle occurs when the list of elements is sorted. Binary search starts by comparing the target element with the middle element of the list. Much like winning the lottery, finding the target element in the middle of a sorted list during a binary search is a stroke of incredible luck, resulting in a time complexity of O(1).

If that doesn’t happen, binary search divides the list in half based on whether the target element is greater or less than the middle element. This process is repeated until the target element is found or the search space is exhausted. With each iteration, binary search effectively halves the search space, eliminating unnecessary portions of the list. This remarkable efficiency results in an upper bound of O(log n) for the time complexity, where n is the number of elements in the list. A code snippet would help us to recall the description.

def binary_search(lst, value):
    low = 0
    high = len(lst) - 1

    while low <= high:
        # Prevents potential integer overflow
        mid = low + (high - low)//2
        if lst[mid] == value:
            return mid
        elif lst[mid] < value:
            low = mid + 1
        else:
            high = mid - 1

    return -1

Hashing with Separate Chaining (Linked List):

Hashing is a powerful method for achieving constant-time storage and retrieval of values. But it depends on the implementation details. A prime example of this is found in Python’s Dictionary and Set, which effectively utilize this technique. Consider the following code snippet:

class Node():
    def __init__(self, value):
        self.value = value
        self.next = None


class HashTable(object):
    def __init__(self):
        self.size = 8  # Considering a fixed sized table.
        self.hash_table = [None] * self.size

    def add(self, lst):
        for value in lst:
            hashed_index = hash(value) % self.size
            if not self.hash_table[hashed_index]:
                self.hash_table[hashed_index] = Node(value)
            else:
                current = self.hash_table[hashed_index]
                while current.next:
                    current = current.next
                current.next = Node(value)

    def lookup(self, val):
        hashed_index = hash(val) % self.size
        current = self.hash_table[hashed_index]
        while current:
            if val == current.value:
                return 'Found'
            else:
                current = current.next
        return 'Not Found'

There is room for improvement, and we will address each point one by one.

• A good hash function is critical to the success of efficient hashing. If the hash function distributes values uniformly, the chances of collision are minimized.
• In this implementation, we handle collisions using separate chaining. This means that multiple values at the same hashed index are stored in a linked list. In the worst case, finding a value would take O(k) time, where k is the length of the longest linked list.
• By replacing the linked list with a binary search tree (BST), the average time complexity improves to O(log k) for a balanced tree. However, if the BST becomes unbalanced, the complexity degrades to O(k). For instance, inserting sorted items into a BST leads to an unbalanced structure, effectively turning it into a linked list. We can take advantage of an AVL (Self Balancing BST), Red Black Tree etc. to keep it balanced for such scenario.
• The hash table in this implementation has a fixed size. Even with a good hash function that distributes values uniformly, collisions are inevitable as more elements are added. Dynamically resizing the hash table can mitigate this issue. Though resizing and rehashing occur infrequently, they result in amortized time complexity, ensuring that the overall time complexity remains close to constant for most operations.

Pattern Based Searching:

There’s a bit more to it. Not that long ago, while implementing binary search for solving a problem I wondered if a pattern is exploited there, would we really need a searching algorithm there?

Get Parijat Purohit’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The answer is NO.

l = [1,2,3,4,5,...,100]

Consider a list l containing consecutive integers starting from 1 to 100, how can you determine the index of a specific number?

To find the index of a number in a list of consecutive integers starting from 1 to 100, you can use the following formula:

Index = Number -1

This formula works because indexing typically starts at 0 in programming languages. So, the first element in the list has an index of 0, the second element has an index of 1, and so on. By subtracting 1 from the desired number, you effectively calculate its position in the list.For example, the index of the number 67 would be 67 -1 = 66.

Consider another arithmetic progression.

3, 7, 11, 15, 19, 23, 27

The sequence is an arithmetic progression with a common difference of 4 starting from 3. We would apply the following formula to find the index of a target value.

Index = (Target - FirstTerm) / CommonDifference

So, the index of a value 103 would be (103–3)/4 = 25. I know you have a question, “What if the value doesn’t exist in this progression?”. If so, then we would get a fraction while calculating the index. Consider a non existent value 105, the formula would give us 25.5.

Do you remember the time complexity of the best case scenarios we were talking in linear search and binary search? The average time complexity of calculating the index using the formula for an arithmetic progression is same. Yes it is O(1). Hashing can offer O(1) time complexity on average, but it requires careful fine-tuning to achieve optimal performance.

If the pattern (or formula) governing the sorted elements can be determined from the initial elements or is explicitly stated in the problem, the search space can often be efficiently explored in constant time.

References:

1. Cormen, Thomas H., et al. Introduction to algorithms. MIT press, 2022.
2. Zaczyński, Bartosz. “How to Do a Binary Search in Python” Real Python, https://realpython.com/binary-search-python/. Accessed [06.03.2025].