Search Algorithms: Types, How They Work, and Which to Use

A search algorithm finds a target value inside a data structure. The main types of search algorithms are linear, binary, jump, interpolation, exponential, ternary, Fibonacci and hash based search. Linear search works on any data in O(n). The interval algorithms, led by binary search at O(log n), are much faster but need sorted data. Hash based search is fastest for exact matches at O(1) on average, at the cost of extra memory. Choose by asking whether your data is sorted, how big it is, and whether you need exact matches or ranges.

Every app you use is quietly running a search. When you look up a contact, filter a product list or type into a site's search box, an algorithmic search is deciding, step by step, where the answer is and how quickly to reach it. This guide from Course Unbox explains what search algorithms are, the main types, how fast each one is, and how to choose the right one.

What is searching, and what is a search algorithm?

Searching is the operation of finding whether a particular value exists in a collection of data, and if it does, where it sits. That collection might be an array, a linked list, a tree, a database table or a file. The searching operation is one of the most common tasks in computing, which is why so much effort has gone into making it fast.

A search algorithm is the step by step method that carries out that operation. Two measures tell you how good it is. Time complexity describes how the number of steps grows as the data grows, written in Big O notation, and space complexity describes how much extra memory the algorithm needs. In short, the whole point of what is searching is to reach the answer in as few comparisons as possible.

Search algorithms vs sorting vs search engine algorithms

Three terms sound alike and get mixed up, so it is worth separating them before we go further.

• Search algorithms find an item in a collection. That is the subject of this guide.

• Sorting algorithms arrange items in order, such as smallest to largest. Sorting and searching are close cousins, because many fast search algorithms only work on sorted data, so a sort often runs first.

• Search engine algorithms are a different thing entirely. When people use the phrase algorithmic search about Google or Bing, they usually mean the ranking systems that decide which web pages to show.

This page is about the first meaning, the classical algorithms that locate a value inside a data structure. If you want the search engine meaning instead, that is the world of search engine optimisation, covered in the Course Unbox SEO course. For a formal definition of the general concept, see the Wikipedia entry on search algorithms.

The three families of search algorithms

Almost every search algorithm belongs to one of three families, and knowing which family a problem needs is most of the battle.

• Sequential search checks elements one at a time. It makes no assumption about order, so it works on any data, but it is slow on large sets. Linear search is the example.

• Interval search uses the order of sorted data to throw away large chunks of the collection at each step. Binary, jump, interpolation, exponential, ternary and Fibonacci search all belong here. They are far faster, but they need the data sorted first.

• Hashing maps a value straight to its location using a hash function, giving near instant lookups on average, at the cost of extra memory.

The main types of search algorithms

Here are the eight algorithms you will meet most often, with how each works, how fast it is, and when to reach for it.

1. Linear (sequential) search

Linear search checks each element from the start until it finds the target or reaches the end. It is the simplest search algorithm and the only common one that works on unsorted data. Time complexity is O(n) on average and in the worst case, and O(1) if the target is first. Space is O(1). Use it for small lists, unsorted data, or a single search where sorting first would not pay off.

2. Binary search

Binary search works on a sorted array. It checks the middle element and, because the data is ordered, discards the half that cannot contain the target, then repeats. This divide and conquer approach halves the search space every step. Time complexity is O(log n) in the worst case and O(1) at best, with O(1) extra space for the iterative version. It is the workhorse of the interval family, and you can read the full method on the Wikipedia binary search page.

3. Jump search

Jump search also needs a sorted array. It jumps ahead in fixed blocks of about the square root of the array size, and once it passes the target it runs a linear search back through the last block. Time complexity is O(√n) and space is O(1). It is useful when jumping backward is expensive, such as on some external storage.

4. Interpolation search

Interpolation search improves on binary search when the data is sorted and evenly distributed. Instead of always checking the middle, it estimates where the target should be using a formula, the way you open a dictionary near the back to find the word zebra. Its average time complexity is O(log log n) for uniformly distributed data, but it can fall to O(n) in the worst case when the data is skewed. Space is O(1).

5. Exponential search

Exponential search, also called doubling or galloping search, finds a range where the target could be by doubling an index, 1, 2, 4, 8 and so on, until it overshoots, then runs binary search inside that range. Time complexity is O(log n) and space is O(1). It shines on unbounded or very large sorted data where the size is not known up front.

6. Ternary search

Ternary search divides a sorted range into three parts rather than two. It is O(log n), but it makes more comparisons per step than binary search, so in practice binary search is usually faster. Its main use is finding the maximum or minimum of a unimodal function.

7. Fibonacci search

Fibonacci search splits a sorted array using Fibonacci numbers instead of the midpoint. It runs in O(log n) and uses only addition and subtraction, no division, and touches memory in a cache friendly pattern, which can help on very large arrays.

8. Hash based search

Hash based search does not scan or divide at all. A hash function converts the key into an index in a hash table, so the value is found in roughly one step. Time complexity is O(1) on average and O(n) in the rare worst case when many keys collide, with O(n) space for the table. It is the fastest option for exact match lookups, and it is how dictionaries, sets and database indexes work, but it does not keep data in order, so it cannot answer range queries.

Search algorithm comparison: time and space complexity

This table is the quick reference. Best case, average case and worst case are time complexity, in Big O notation.

Interpolation search reaches O(log log n) only when the sorted data is uniformly distributed. For deeper worked examples of each algorithm, the GeeksforGeeks searching algorithms hub is a good reference, and the Big-O Cheat Sheet plots how each complexity class grows.

How to choose the right search algorithm

You rarely need all eight. A few questions get you to the right one.

• Is the data unsorted and small, or searched only once? Use linear search and skip the cost of sorting.

• Is the data sorted, or searched often enough to justify sorting once? Use binary search as the default.

• Is the sorted data large and uniformly distributed numeric keys? Interpolation search can beat binary search.

• Is the size unknown or unbounded? Use exponential search to find the range, then binary search inside it.

• Do you only need exact match lookups, order does not matter, and memory is available? Use hashing for O(1) average lookups.

• Do you need range or nearest neighbour queries? Keep the data sorted and use binary search or a tree, not a hash, because hashing loses order.

Where search algorithms are used

Search algorithms are not just an exam topic. They sit under most of the software you use every day. Database indexes use B-tree structures and hashing to find rows fast. File systems and operating systems search directories and tables constantly. Search engines, GPS and routing apps, autocomplete, e commerce filters and many machine learning steps all lean on the same ideas. Even the git bisect command, which finds the commit that introduced a bug, is a binary search over your project history.

Search in AI and in search engines

Two neighbouring topics often get bundled with this one. In artificial intelligence, search means exploring a space of possible states or moves, using methods such as breadth first search, depth first search and heuristic search. That is a large field of its own. In digital marketing, algorithmic search usually means how a search engine ranks pages, which is the domain of search engine optimisation. If those directions interest you, the Course Unbox AI Digital Marketing course covers how modern AI search and ranking work, the Full Stack Development course covers the data structures and algorithms behind everyday software, and you can browse the full Course Unbox course catalogue to find the right fit.