Searching Algorithm & Their Complexity Complexity 🔎

🔎 Searching Algorithm & Their Complexity

Searching algorithms are used to locate a specific element within a collection of data. Depending on the data structure and whether the data is sorted, different algorithms offer different trade-offs between speed, memory usage, and implementation complexity. Unlike sorting algorithms, stability is not a meaningful property for searching algorithms.

Stability is a characteristic of sorting algorithms, describing whether equal elements preserve their original relative order after sorting. Since searching algorithms do not rearrange elements, the concept of stability does not apply.

The following table compares the most common searching algorithms and data structures based on their time and space complexity.

Searching Algorithm & Their Complexity

#	Algorithm	⏱️ Best	⚖️ Average	🔻 Worst	💾 Space	📋 Sorted Required
1	🚶‍♂️ Linear Search	$O(1)$	$O(n)$	$O(n)$	$O(1)$	❌ No
2	✂️ Binary Search	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$	✅ Yes
3	🎯 Hash Table Lookup (Map)	$O(1)$	$O(1)$	$O(n)$	$O(n)$	❌ No
4	🌲 Binary Search Tree (Unbalanced BST)	$O(1)$	$O(\log n)$	$O(n)$	$O(n)$	❌ No
5	🎄 Balanced BST (AVL, Red-Black)	$O(1)$	$O(\log n)$	$O(\log n)$	$O(n)$	❌ No

Notes

• Binary Search requires sorted data.
• Hashing gives average constant-time lookup but degrades to $O(n)$ on hash collisions..
• Hash Table (Map) requires $O(n)$ space because it stores additional hash buckets.
• Balanced Trees ensure logarithmic performance by maintaining structure.
• BSTs maintain their own ordering internally, so you don't need to provide a pre-sorted collection. They dynamically organize elements as they're inserted.

Less Common Searching Algorithm & Their Complexity

#	Algorithm	⏱️ Best	⚖️ Average	🔻 Worst	💾 Space	📋 Sorted Required
1	🦘 Jump Search	$O(1)$	$O(\sqrt{n})$	$O(\sqrt{n})$	$O(1)$	✅ Yes
2	📶 Interpolation Search	$O(1)$	$O(\log \log n)$	$O(n)$	$O(1)$	✅ Yes
3	📈 Exponential Search	$O(1)$	$O(\log n)$*	$O(\log n)$	$O(1)$	✅ Yes
4	🔢 Fibonacci Search	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$	✅ Yes
5	🔱 Ternary Search	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$	✅ Yes

Notes

• Jump and Interpolation searches are useful for uniformly distributed data.
• Exponential Search has an average complexity of $O(\log i)$, where $i$ is the position of the target element. This is often written as $O(\log n)$ for simplicity because the worst case occurs when the target is near the end of the array.
• Jump Search is generally slower than Binary Search but faster than Linear Search on sorted arrays.
• Interpolation Search performs exceptionally well on uniformly distributed data, achieving an average complexity of $O(\log \log n)$.
• Exponential Search is ideal for unbounded or unknown-sized sorted arrays.
• Fibonacci Search has similar complexity to Binary Search but uses Fibonacci numbers instead of repeatedly halving the search range.
• Ternary Search is usually not recommended for searching arrays because Binary Search performs fewer comparisons. Its primary application is optimizing unimodal functions, not array searching.

---

1. Linear Search 🚶‍♂️

Linear search checks each element in a list sequentially until the target is found or the list is exhausted.

Linear Search is the simplest searching algorithm.

When to Use Linear Search

• The data is unsorted.
• The dataset is small.
• You only need to perform occasional searches.
• Simplicity is more important than performance.

Linear Search Complexity

Case	Complexity
Best	$O(1)$ (first element matches)
Average	$O(n)$
Worst	$O(n)$ (last element or not found)

Implementation

It checks each element in a collection one by one until it finds the target value or reaches the end.

     linearSearch =(inputArray, target) => {
        for (let index = 0; index < inputArray.length; index++) {
          
            if (inputArray[index] === target) {
                console.log(`Found ${target} at index ${index}`);
                return  index
a            }
        }

    console.log(`${target} not found`);
    return -1;
    }

---

2. Binary Search ✂️

Binary Search is a divide-and-conquer algorithm that repeatedly divides a sorted array in half until it finds the target value.

Requirement

• The array must be sorted.

Avoid binary search if:

• The data is unsorted (unless you sort it first).
• You frequently insert or delete elements from an array, making it costly to keep the array sorted.

Use binary search when:

• The data is sorted.
• You need to perform many searches.
• The dataset is large.
• Fast lookup time is important.

Binary Search Complexity

Case	Time
Best	$O(1)$
Average	$O(\log n)$
Worst	$O(\log n)$

Iterative Implementation

It keeps dividing the list till item is found or not

   binarySearch = (inputArray, target) => {
        let left = 0;
        let right = inputArray.length - 1;

        while (left <= right) {
            const mid = Math.floor((left + right) / 2);

            if (inputArray[mid] === target) {
                console.log(`Found ${target} at index ${mid}`);
                return mid;
            } else if (inputArray[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        console.log(`${target} not found`);
        return -1;
    }

Recursive implementation

   
     binarySearchRecursive = (arr, target, left = 0, right = arr.length - 1)=> {
        if (left > right) {
            return -1;
        }
    
        const mid = Math.floor((left + right) / 2);
    
        if (arr[mid] === target) {
            return mid;
        }
    
        if (target < arr[mid]) {
            return binarySearchRecursive(arr, target, left, mid - 1);
        }
    
        return binarySearchRecursive(arr, target, mid + 1, right);
    }

---

3. Hash Table Lookup (Map) 🎯

A Hash Table stores data as key-value pairs and uses a hash function to compute where each key should be stored.

Instead of searching through every element, it computes the key's location and retrieves the value directly.

Hash Function
    │
    ▼
Key: 103
    │
    ▼
+----------------------+
| Bucket 0             |
| Bucket 1             |
| Bucket 2 ── Charlie  |
| Bucket 3             |
| Bucket 4             |
+----------------------+

Hash Table Complexity

Operation	Average	Worst
Search	O(1)	O(n)
Insert	O(1)	O(n)
Delete	O(1)	O(n)

The worst case occurs when many keys collide and end up in the same bucket. In that case Hash table need to expand

Use case

Hash Tables are generally preferred for fast key-based lookups

Hash tables are one of the most widely used data structures in software development.

• JavaScript Map
• Python dict
• Java HashMap
• C++ unordered_map
• Go map

---

4. Binary Search Tree (Unbalanced BST) 🌲

Each node has at most two children and follows the BST property:

• All values in the left subtree are less than the current node.
• All values in the right subtree are greater than the current node.

Left Subtree < Node < Right Subtree

To search for a value:

• Start at the root.
• If the target equals the current node, return it.
• If the target is smaller, search the left subtree.
• If the target is larger, search the right subtree.
• Repeat until the value is found or the tree ends.

      50 
     /   \ 
    30   70
   / \   / \ 
  20 40 60 80

If values are inserted in sorted order unbalanced BST turned into a list.

    10 
      \ 
       20 
         \ 
          30 
            \ 
             40 
               \ 
                50

Unbalanced Tree Complexity

Operation	Average	Worst Case
Search	$O(\log n)$	$O(n)$
Insert	$O(\log n)$	$O(n)$
Delete	$O(\log n)$	$O(n)$

BST vs Binary Search

Binary Search is ideal for static, sorted arrays where the data rarely changes.

A Binary Search Tree is a better choice when the dataset is dynamic because it supports efficient searching, insertion, and deletion, each with an average time complexity of $O(\log n)$.

However, if the tree becomes unbalanced, these operations can degrade to $O(n)$, which is why self-balancing trees such as AVL Trees and Red-Black Trees are commonly used in practice.

---

5. Balanced BST (AVL, Red-Black) 🎄

A Balanced Binary Search Tree (Balanced BST) is a Binary Search Tree that automatically maintains its height to ensure efficient searching, insertion, and deletion.

Unlike a regular BST, a Balanced BST prevents the tree from becoming skewed, guaranteeing that operations remain fast even after many insertions and deletions.

Common implementations include:

• AVL Tree
• Red-Black Tree

This predictable performance makes balanced trees the preferred choice for ordered collections that are frequently updated.

Balanced BST Complexity

A Balanced BST guarantees:

$$\text{Search} = \text{Insert} = \text{Delete} = O(\log n)$$

making it an excellent choice for dynamic ordered data.

Operation	Complexity
Search	$O(\log n)$
Insert	$O(\log n)$
Delete	$O(\log n)$

AVL Tree vs Red-Black Tree

Feature	AVL Tree	Red-Black Tree
Balance	More strict	Less strict
Search	Slightly faster	Very fast
Insert/Delete	More rotations	Fewer rotations
Used In	Databases, memory indexes	Java TreeMap, C++ std::map, Linux Kernel

---

Unpopular Sorting Algos

These are some unpopular sorting algos who are still taught but have very limited practical applications

Binary Search can outperform every one of this algos on a modern computer. But they can give edge while optimizing.

Note: They all Requires a Sorted Array

1. JumpSearch 🦘

Instead of checking every element, it jumps ahead by a fixed step size (typically √n) until it passes the target, then performs a linear search within that block.

Requirement

• The array must be sorted.

JumpSearch Complexity

Case	Time
Best	$O(1)$
Average	$O(\sqrt n)$
Worst	$O(\sqrt n)$

Why is Jump Search better than Linear?

Suppose you have 10,000 elements.

Linear Search

• Worst case: 10,000 comparisons

Jump Search

$$\text{Jump Size} = \sqrt{10000} = 100 \text{ jumps}$$

• Then 100 linear comparisons
• Total ≈ 200 comparisons

Binary Search

$$\log_{2}(10000) \approx 13.29 \approx 14 \text{ comparisons}$$

Algorithm	Approximate Comparisons
Linear	10,000
Jump	200
Binary	14

Historically, Jump Search was useful when:

• Sequential access was much faster than random access.
• Storage media made jumping expensive but predictable.
• Binary search's random memory access wasn't ideal.

On modern computers with arrays in memory, Binary Search almost always wins.

Implementation

 jumpSearch = (inputArray, target) => {
  const n = inputArray.length;
  const step = Math.floor(Math.sqrt(n));

  let prev = 0;
  let current = step;

  // Jump until target could be in the block
  while (current < n && inputArray[current - 1] < target) {
    prev = current;
    current += step;
  }

  // Linear search inside the block
  for (let i = prev; i < Math.min(current, n); i++) {
    if (inputArray[i] === target) {
      return i;
    }
  }

  return -1;
}

---

2. Interpolation Search 📶

It tries to interpolate position based on distribution

Interpolation Search is an improved searching algorithm for sorted and uniformly distributed data.

Instead of always checking the middle element like Binary Search, it estimates where the target is likely to be based on its value.

$$\text{position} = \text{low}+ \frac{(\text{target}-\text{arr[low]}) \times (\text{high}-\text{low})} {\text{arr[high]}-\text{arr[low]}}$$

Requirement

• The array must be sorted.
• Values should be roughly evenly distributed.

A skew distribution can make poor estimates and degrade toward $O(n)$ performance.

Use Interpolation Search if:

• The array is sorted.
• Values are uniformly distributed (e.g., IDs, timestamps, sequential numbers).
• Fast average lookup is important.

Avoid Interpolation Search if:

• Values are clustered or highly uneven. eg: [1,2,3,4,5,6,7,1000]
• The data is unsorted.
• You need guaranteed $O(\log n)$ performance. Binary Search is the safer choice.

Interpolation Search Complexity

Case	Complexity	Comment
Best	$O(1)$	First Item
Average (uniform distribution)	$O(\log \log n)$	Only in uniformly distributed sorted list
Worst	$O(n)$	Skewed data list

Implementation

     interpolationSearch = (inputArray, target)=>{
      let low = 0;
      let high = inputArray.length - 1;
    
      while (
        low <= high &&
        target >= inputArray[low] &&
        target <= inputArray[high]
      ) {
          
        if (low === high) {
          return inputArray[low] === target ? low : -1;
        }
    
        const pos =
          low +
          Math.floor(
            ((target - inputArray[low]) * (high - low)) /
            (inputArray[high] - inputArray[low])
          );
    
        if (inputArray[pos] === target) {
          return pos;
        }
    
        if (inputArray[pos] < target) {
          low = pos + 1;
        } else {
          high = pos - 1;
        }
      }
    
      return -1;
    }

Interpolation Search has a better average-case complexity of $O(\log \log n)$ on uniformly distributed sorted data, so it can outperform Binary Search in those cases.

However, because its performance depends heavily on the data distribution and its worst-case complexity is $O(n)$.

Binary Search is generally preferred in production systems due to its consistent $OO(\log n)$ performance.

---

3. Exponential Search 📈

Exponential Search is a searching algorithm designed for sorted arrays, especially when:

• The array size is unknown or unbounded.
• The target is expected to be near the beginning.

Requirement

• The array must be sorted.

It works in two phases:

1. Find a search range by repeatedly doubling the index.

• Exponentially Expand the search range. Start at index 1 and double each time.

  $$2^0,\;2^1,\;2^2,\;2^3,\;2^4,\;\ldots$$

Index: 1  →  2  →  4  →  8  →  16
Value: 4     6     10    18    Out of bounds

Range found Index 8 (18) and Index 15 (32)

2. Perform Binary Search within that range.

[18,20,22,24,26,28,30,32]

Binary Search quickly finds 22.

Use Exponential Search if:

• The array is sorted.
• The array size is unknown or effectively unbounded (stream or infinite list)
• You're searching in a stream or infinite list.
• The target is expected to be near the beginning.

Avoid Exponential Search if:

• The array size is already known and fixed.

In fixed size array, Binary Search is simpler and just as efficient in the worst case.

Implementation

    
     exponentialSearch=(arr, target)=> {
        const n = arr.length;
        
        if (n === 0) return -1;
        if (arr[0] === target) return 0;
        
        let bound = 1;
        
        while (bound < n && arr[bound] < target) {
        bound *= 2;
        }
        
        let left = Math.floor(bound / 2);
        let right = Math.min(bound, n - 1);
        
        while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
            if (arr[mid] === target) {
              return mid;
            }
        
            if (arr[mid] < target) {
              left = mid + 1;
            } else {
              right = mid - 1;
            }
        }
        
        return -1;
    }

---

4. Fibonacci Search 🔢

Fibonacci Search is a searching algorithm for sorted arrays that uses Fibonacci numbers to divide the search space instead of always using the middle element.

Like Binary Search, it repeatedly reduces the search range, but it chooses probe positions based on the Fibonacci sequence.

$$F(n) = F(n-1) + F(n-2)$$

Requirement

• The array must be sorted.

Deprecated

Fibonacci Search is rarely used today, but it had advantages on older hardware and storage systems.

1. Systems Where Division Is Expensive

Older CPUs performed integer division much more slowly than addition and subtraction.

Fibonacci Search mainly relies on addition and subtraction of Fibonacci numbers.

2. Sequential Storage

On storage media where moving forward is cheaper than jumping randomly (such as magnetic tapes or some disk layouts), Fibonacci Search can reduce costly random seeks.

Modern computer prefer Binary

Binary Search repeatedly computes:

$$\text{mid} = \left\lfloor \frac{\text{left} + \text{right}}{2} \right\rfloor$$

Modern processors compute division quickly, and random memory access is inexpensive for arrays in RAM.

As a result:

• Binary Search is simpler.
• Binary Search is easier to implement.
• Binary Search performs equally well asymptotically.

For these reasons, Binary Search has largely replaced Fibonacci Search in modern software.

Fibonacci Sorting Complexity

Case	Complexity
Best	$O(1)$
Average	$O(\log n)$
Worst	$O(\log n)$

Implementation

 fibonacciSearch = (inputArray, target)=>{
  const n = inputArray.length;

  // Initialize Fibonacci numbers F(n) = F(n-1) + F(n-2)
  let fibMm2 = 0; // (m-2)'th Fibonacci number
  let fibMm1 = 1; // (m-1)'th Fibonacci number
  let fibM = fibMm1 + fibMm2; // m'th Fibonacci number

  // Find the smallest Fibonacci number greater than or equal to n
  while (fibM < n) {
    fibMm2 = fibMm1;
    fibMm1 = fibM;
    fibM = fibMm1 + fibMm2;
  }

  // Marks the eliminated range from the front
  let offset = -1;

  while (fibM > 1) {
    // Check the valid Fibonacci index
    const index = Math.min(offset + fibMm2, n - 1);

    if (inputArray[index] < target) {
      // Move three Fibonacci variables down one step
      fibM = fibMm1;
      fibMm1 = fibMm2;
      fibMm2 = fibM - fibMm1;
      offset = index;
    } else if (inputArray[index] > target) {
      // Move two Fibonacci variables down two steps
      fibM = fibMm2;
      fibMm1 = fibMm1 - fibMm2;
      fibMm2 = fibM - fibMm1;
    } else {
      return index;
    }
  }

  // Check the last possible element
  if (fibMm1 && inputArray[offset + 1] === target) {
    return offset + 1;
  }

  return -1;
}

---

5. Ternary Search 🔱

Instead of splitting the search space into 2 parts like Binary Search, Ternary Search splits it into 3 parts.

Left          Mid1         Mid2          Right
|--------------|-------------|--------------|

You compare the target with both mid1 and mid2 to determine which third to continue searching.

$$\text{mid1} = \text{left} + \frac{\text{right} - \text{left}}{3}$$ $$\text{mid2} = \text{right} - \frac{\text{right} - \text{left}}{3}$$

Requirement

• The array must be sorted.

Ternary Search Complexity

Algorithm	Time Complexity
Binary Search	$(O(\log_2 n))$
Ternary Search	$(O(\log_3 n))$

Why Binary still beats Ternary

Although $(O(\log_3 n))$ appears smaller, Ternary Search performs two comparisons per iteration instead of one.

In practice, Binary Search usually performs fewer comparisons overall and is therefore faster for searching arrays.

Where Ternary Search Really Shines

Ternary Search is commonly used to optimize unimodal functions, where values:

• continuously increase and then decrease (find the maximum)
• continuously decrease and then increase (find the minimum)

Example

• Competitive programming
• Mathematical optimization
• Machine learning hyperparameter tuning
• Physics and engineering optimization problems

---

Related Posts

• 🧱 Data Structures & Big O Complexity — the underlying structures (arrays, BSTs, hash tables) these search algorithms run against
• ⚡ Sorting Algorithm Complexity — Binary Search's sorted-data prerequisite is what a sorting algorithm provides