Searching Algorithms for Beginners: Linear Search and Binary Search

1. Introduction

A searching algorithm is a step-by-step method for finding a particular value, called the target, inside a collection of data. The result is usually one of two things: where the target is (for example, its position in a list), or a clear signal that it is not there.

Searching is one of the most common jobs a program does. When you log in, the application searches for your account. When you open an order, the system searches for that order's record. When an API receives GET /customers/42, the server has to find customer 42 before it can return anything. Most features you build will search for something, even if the search code is hidden inside a library or a database.

Searching shows up across real software:

• ERP systems (enterprise resource planning, software that runs inventory, purchasing, and accounting) look up items by stock code, invoices by number, and suppliers by name.

• CRM systems (customer relationship management) find customers by ID, email, or phone number.

• E-commerce sites search products by name, filter by category, and look up a cart by session.

• Databases find rows that match a condition such as WHERE email = 'asha@example.com'.

• APIs find the resource named in the request, check an API key against stored keys, and look up permissions.

A relatable example. Think about two ways of finding a word in a book.

• If the pages are in random order, the only reliable method is to start at page one and check every page until you find the word. That is linear search.

• A dictionary is in alphabetical order. You can open it in the middle, see that your word comes later, and ignore the whole first half. Repeat that, and you find the word in a few steps. That is binary search.

The difference between the two methods comes from one fact: whether the data is in order. That idea runs through the whole article.

2. Learning Objectives

After completing this article, you will be able to:

• Explain what a searching algorithm is and why software depends on searching.

• Describe how linear search works and implement it in Python and PHP.

• Describe how binary search works, explain why it requires sorted data, and implement it in Python and PHP, both iteratively and recursively.

• Trace each algorithm by hand on a small array.

• Read and use Big-O notation to compare the cost of the two algorithms.

• Choose the right approach for a real task, including when to use a hash table or a database index instead.

• Recognize and avoid the most common beginner mistakes, especially off-by-one errors.

• Write test cases that cover the edge cases of a search function.

3. Prerequisites

You do not need prior algorithm knowledge. You do need these basics:

• Arrays (lists). An array stores values in order. Each value has an index, its position, starting at 0. In [10, 20, 30], the value 10 is at index 0 and 30 is at index 2. In Python this is a list. In PHP it is an array whose keys are 0, 1, 2, ....

• Loops. You should be able to read a for loop that visits every element and a while loop that runs while a condition is true.

• Conditional statements. if, elif/elseif, and else, plus comparisons such as ==, <, and >.

• Functions. Defining a function with parameters and returning a value.

• Basic programming concepts. Variables, integer division (dividing and dropping the remainder, such as 7 // 2 == 3 in Python or intdiv(7, 2) in PHP), and running a script from the command line.

If you understand what this line does, you are ready:

It prints each position alongside its value: 0 10, 1 20, 2 30.

for index, value in enumerate([10, 20, 30]):print(index, value)

4. Types of Searching Algorithms

A quick word on Big-O notation

Before comparing algorithms, we need a way to describe how much work they do. Big-O notation describes how the number of steps grows as the input grows. It ignores small details and focuses on the overall trend. Here, n means the number of elements in the collection.

• O(1), "constant time": the work stays the same no matter how large n is.

• O(log n), "logarithmic time": the work grows very slowly. Here, log n means roughly how many times you can cut n in half before you reach 1. For 1,000,000 elements, that is about 20.

• O(n), "linear time": the work grows in direct proportion to n. Twice the data means about twice the work.

Big-O describes growth, not seconds. It tells you how an algorithm behaves as data gets large. It does not tell you exactly how fast a specific program runs on a specific computer.

We also describe three situations:

• Best case: the luckiest possible input.

• Average case: what to expect on typical input.

• Worst case: the unluckiest input. This is usually the most important case, because it is the guarantee.

A. Linear Search

Definition and working principle

Linear search (also called sequential search) checks each element one by one, from the start of the collection, until it finds the target or runs out of elements.

It makes no assumptions about the data. The collection can be in any order.

Step-by-step example

Search for 4 in this array:

Index: 0 1 2 3 4

Value: 7 2 9 4 5

1. Check index 0: value 7. Not 4, so move to the next element.

2. Check index 1: value 2. Not 4, so move on.

3. Check index 2: value 9. Not 4, so move on.

4. Check index 3: value 4. Match. Return index 3.

If we searched for 8 instead, we would check all five elements, find no match, and return -1. In this article, -1 means "not found". It is a safe signal because -1 is never a valid index.

Pseudocode

Pseudocode is a plain-language description of an algorithm that is not tied to any programming language.

function linearSearch(items, target):

for each index i from 0 to length(items) - 1:

if items[i] equals target:

return i

return -1

Implementation in Python

def linear_search(items, target):for index, value in enumerate(items):if value == target:return indexreturn -1numbers = [7, 2, 9, 4, 5]print(linear_search(numbers, 4)) # 3print(linear_search(numbers, 8)) # -1

Line by line:

• def linear_search(items, target): defines a function that takes the collection and the value to find.

• for index, value in enumerate(items): visits each element. enumerate gives both the position (index) and the element (value).

• if value == target: compares the current element with the target.

• return index stops the search immediately and returns the position of the first match.

• return -1 runs only if the loop finished without finding a match.

Implementation in PHP

<?phpdeclare(strict_types=1);function linearSearch(array $items, mixed $target): int{foreach ($items as $index => $value) {if ($value === $target) {return $index;}}return -1;}$numbers = [7, 2, 9, 4, 5];echo linearSearch($numbers, 4), PHP_EOL; // 3echo linearSearch($numbers, 8), PHP_EOL; // -1

Line by line:

• declare(strict_types=1); makes PHP enforce the declared parameter and return types instead of silently converting values.

• function linearSearch(array $items, mixed $target): int accepts an array and a target of any type, and promises to return an integer.

• foreach ($items as $index => $value) visits each element with its key. For a normal list such as [7, 2, 9], the key is the position.

• if ($value === $target) uses strict comparison (===), which checks both value and type. With loose comparison (==), PHP converts types before comparing, so "4" == 4 is true. Strict comparison avoids surprising matches.

• return -1; signals that the target was not found.

This function expects a list whose keys are 0, 1, 2, .... If your array has other keys, such as ['a' => 7, 'b' => 2], call array_values() on it first.

Time and space complexity

Space complexity: O(1). The function uses a fixed number of variables (index and value) no matter how large the array is.

Advantages, disadvantages, and use cases

Advantages

• Works on unsorted data.

• Very simple to write and hard to get wrong.

• Works on any collection you can walk through from start to finish, including linked lists and data read line by line from a file.

• Needs no extra memory and no preparation step.

Disadvantages

• Slow for large collections when you search them many times, because each search may check every element.

Practical use cases

• Small lists, such as a dropdown of a dozen options.

• One-off searches through unsorted data.

• Searches with a condition, such as "find the first order over $500", where the data is not sorted by that field.

• Partial text matches, such as "product names containing lap". Ordering does not help with a match in the middle of a word.

B. Binary Search

Definition and working principle

Binary search finds a target in a sorted collection by repeatedly checking the middle element and discarding the half that cannot contain the target.

Each comparison has three possible outcomes:

• The middle element equals the target: done.

• The middle element is smaller than the target: the target, if present, must be to the right. Discard the left half.

• The middle element is larger than the target: the target, if present, must be to the left. Discard the right half.

Every step removes about half of the remaining elements. That is why binary search is fast.

Why the input must be sorted

Binary search relies on one promise: every element to the left of the middle is less than or equal to it, and every element to the right is greater than or equal to it. Only sorted data keeps that promise.

On unsorted data, discarding a half is a guess, not a deduction. For example, search for 9 in [7, 2, 9, 4, 5], which is unsorted:

• The middle element (index 2) is 9. We get lucky.

Now search for 7:

• The middle element is 9. Because 7 < 9, binary search discards the right half and searches [7, 2].

• The middle of [7, 2] is 7. Found, by luck again.

Now search for 5:

• The middle element is 9. Because 5 < 9, binary search discards the right half, which is exactly where 5 is.

• It searches [7, 2], does not find 5, and wrongly reports "not found".

Binary search on unsorted data does not crash. It quietly returns wrong answers, which is worse.

The low, high, and mid variables

Binary search tracks the part of the array that might still contain the target. That part is called the search space.

• low is the index of the first element still in the search space. It starts at 0.

• high is the index of the last element still in the search space. It starts at len(items) - 1.

• mid is the index halfway between them: (low + high) // 2. Integer division rounds down, so mid is always a whole number.

The search space is every index from low to high, including both ends. When low becomes greater than high, the search space is empty and the target is not present.

Step-by-step example

Search for 23 in this sorted array:

Index: 0 1 2 3 4 5 6

Value: 3 8 12 17 23 31 42

1. low = 0, high = 6, mid = (0 + 6) // 2 = 3. items[3] is 17. Since 17 < 23, the target must be to the right. Set low = mid + 1 = 4.

2. low = 4, high = 6, mid = (4 + 6) // 2 = 5. items[5] is 31. Since 31 > 23, the target must be to the left. Set high = mid - 1 = 4.

3. low = 4, high = 4, mid = 4. items[4] is 23. Match. Return 4.

Binary search needed 3 comparisons. Linear search would have needed 5, checking indexes 0 through 4.

We use mid + 1 and mid - 1, not mid, because items[mid] has already been checked and is not the target. Keeping it in the search space would waste a step, and as Section 8 shows, it can cause an infinite loop.

Pseudocode

function binarySearch(items, target):

low = 0

high = length(items) - 1

while low <= high:

mid = floor((low + high) / 2)

if items[mid] equals target:

return mid

else if items[mid] < target:

low = mid + 1

else:

high = mid - 1

return -1

Implementation in Python (iterative)

def binary_search(items, target):low = 0high = len(items) - 1while low <= high:mid = (low + high) // 2if items[mid] == target:return midif items[mid] < target:low = mid + 1else:high = mid - 1return -1sorted_numbers = [3, 8, 12, 17, 23, 31, 42]print(binary_search(sorted_numbers, 23)) # 4print(binary_search(sorted_numbers, 20)) # -1

Line by line:

• low = 0 and high = len(items) - 1 make the search space the whole array. For an empty array, high is -1, so the loop never runs and the function returns -1. The empty case is handled with no special code.

• while low <= high: continues as long as at least one element remains. The <= matters: when low == high, exactly one element is left, and it still needs to be checked.

• mid = (low + high) // 2 finds the middle index, rounding down.

• if items[mid] == target: return mid returns the position on a match.

• if items[mid] < target: low = mid + 1 discards the left half, including mid.

• else: high = mid - 1 discards the right half, including mid.

• return -1 runs when the search space is empty.

Implementation in PHP (iterative)

<?phpdeclare(strict_types=1);function binarySearch(array $items, int $target): int{$low = 0;$high = count($items) - 1;while ($low <= $high) {$mid = intdiv($low + $high, 2);if ($items[$mid] === $target) {return $mid;}if ($items[$mid] < $target) {$low = $mid + 1;} else {$high = $mid - 1;}}return -1;}$sortedNumbers = [3, 8, 12, 17, 23, 31, 42];echo binarySearch($sortedNumbers, 23), PHP_EOL; // 4echo binarySearch($sortedNumbers, 20), PHP_EOL; // -1

The logic matches the Python version line for line. PHP-specific details:

• count($items) returns the number of elements.

• intdiv($low + $high, 2) performs integer division. Plain / in PHP can return a float, such as 7 / 2 === 3.5, and a float cannot be used as an array position the way we need.

• The function is typed for integers to keep comparisons predictable. To search sorted strings, compare them with strcmp(), and make sure the array was sorted with the same comparison.

• The array must be a sorted list with keys 0, 1, 2, .... sort($items) produces exactly that.

A note on mid in other languages. In Java, C, C++, and C#, integers have a fixed maximum size. For very large arrays, low + high can exceed that maximum, which is called overflow. In those languages, write mid = low + (high - low) / 2, which gives the same result without overflowing. Python integers have no fixed size, and PHP's 64-bit integers are far larger than any array index, so the simple form is safe in both.

Iterative vs recursive implementations

The versions above are iterative: they use a loop. Binary search can also be written recursively: the function calls itself on the smaller half.

Python (recursive):

def binary_search_recursive(items, target, low=0, high=None):if high is None:high = len(items) - 1if low > high:return -1mid = (low + high) // 2if items[mid] == target:return midif items[mid] < target:return binary_search_recursive(items, target, mid + 1, high)return binary_search_recursive(items, target, low, mid - 1)

PHP (recursive):

<?phpdeclare(strict_types=1);function binarySearchRecursive(array $items, int $target, int $low = 0, ?int $high = null): int{$high ??= count($items) - 1;if ($low > $high) {return -1;}$mid = intdiv($low + $high, 2);if ($items[$mid] === $target) {return $mid;}if ($items[$mid] < $target) {return binarySearchRecursive($items, $target, $mid + 1, $high);}return binarySearchRecursive($items, $target, $low, $mid - 1);}

How the recursive version works:

• On the first call, high is not provided, so it defaults to the last index. In Python, high=None cannot default directly to len(items) - 1, because a default value cannot refer to another parameter. The function checks for None instead. PHP's $high ??= ... assigns a value only when $high is null.

• if low > high: return -1 is the base case, the condition that stops the recursion. It means the search space is empty.

• Each recursive call passes a smaller search space. Every call removes about half of what remains, so the recursion ends after about log n calls.

Comparison:

A stack frame is the memory a running function uses for its local variables. Each recursive call adds one frame until the calls return. For binary search, the depth is about 30 even for a billion elements, so there is no practical risk of exceeding Python's default recursion limit of 1,000. Neither Python nor PHP optimizes away these frames. Prefer the iterative version in production code: it uses constant memory and is easier to step through in a debugger. Learn the recursive version because it shows the divide-and-conquer idea clearly.

Time and space complexity

Space complexity: O(1) iterative, O(log n) recursive.

For a sorted array of n elements, binary search makes at most floor(log2(n)) + 1 comparisons with the middle element. The table compares the worst-case count with linear search. These are comparison counts derived from the algorithms, not timing measurements.

Advantages, disadvantages, and use cases

Advantages

• Very few comparisons, even for huge collections.

• Predictable worst case of O(log n).

• Needs no extra memory in the iterative form.

• The same halving idea extends to many problems, such as finding the first matching element or the position where a new value should be inserted.

Disadvantages

• Requires sorted data. Sorting costs O(n log n) time with a good general-purpose algorithm, which is more than one linear search.

• Keeping an array sorted while inserting new values is costly: each insert may shift many elements.

• Requires random access, meaning jumping straight to any index. Arrays support this; linked lists do not, so binary search is a poor fit for them.

• Easy to get subtly wrong, because of boundaries and off-by-one errors.

Practical use cases

• Searching a sorted list that is built once and searched many times, such as a list of country codes or product SKUs loaded at startup.

• Finding where a value belongs in a sorted list. Python's bisect module does exactly this.

• Finding values in sorted ranges, such as "the first log entry after 10:00".

• Understanding database indexes, which use a related idea (Section 7).

5. Visual Walkthrough

Both algorithms use the same sorted array, so you can compare them directly:

Index: 0 1 2 3 4 5 6

Value: 3 8 12 17 23 31 42

Linear search for 23 (found)

Linear search moves forward one element at a time because it learns nothing about the rest of the array from each check. Even though the array is sorted, this version does not use that fact.

Binary search for 23 (found)

Step 1: [ 3 8 12 (17) 23 31 42 ] low=0 high=6 mid=3 17 < 23 -> discard left half

Step 2: [ 23 (31) 42 ] low=4 high=6 mid=5 31 > 23 -> discard right half

Step 3: [(23)] low=4 high=4 mid=4 23 = 23 -> return 4

Each decision is a deduction, not a guess. In step 1, 17 < 23 and the array is sorted, so every element at index 0–3 is at most 17 and none can be 23. They are removed for certain.

Binary search for 20 (not found)

After three comparisons the search space is empty, and binary search can say with certainty that 20 is not present. Linear search would need all 7 comparisons to reach the same conclusion.

6. Algorithm Comparison

Big-O in plain language:

• O(1) is like reaching for a book you already hold: the size of the library does not matter.

• O(log n) is like the dictionary method: doubling the size of the book adds only one more step.

• O(n) is like reading every page: doubling the book doubles the work.

Big-O describes growth, not speed in seconds. For a list of 10 items, the difference between the two algorithms is too small to matter in most programs. For millions of items searched thousands of times, it is the difference between a feature that scales and one that does not.

7. Real-World Software Development Examples

Two different worlds: in-memory collections and databases

Searching an in-memory collection means your program already holds the data, in a Python list or a PHP array, and your code or a language function walks through it. You choose the algorithm.

Searching a database means you describe what you want in a query, and the database engine decides how to find it. Performance depends on indexes and on the query execution plan, not on a loop you write. Both ideas are explained below.

Finding a customer by ID

In memory, searched once: a linear search is fine.

customers = [{"id": 101, "name": "Ravi"},{"id": 102, "name": "Asha"},{"id": 103, "name": "Mina"},]

def find_customer(customers, customer_id):for customer in customers:if customer["id"] == customer_id:return customerreturn Noneprint(find_customer(customers, 102)) # {'id': 102, 'name': 'Asha'}

In memory, searched many times: build a hash table once. A hash table stores values under keys and finds a key in O(1) time on average. Python's dict and PHP's associative arrays are hash tables.

customers_by_id = {customer["id"]: customer for customer in customers}print(customers_by_id.get(102)) # {'id': 102, 'name': 'Asha'}$customersById = array_column($customers, null, 'id');$customer = $customersById[102] ?? null;

Building the table takes O(n) time once. After that, each lookup by exact key is O(1) on average. For exact-match lookups, a hash table usually beats both linear and binary search.

Finding a product by name

Product search usually means a partial, case-insensitive match, such as "lap" matching "Laptop Stand". Sorting does not help with a match in the middle of a word, so a linear scan is the right in-memory approach.

products = ["Desk Lamp", "Laptop Stand", "Office Chair", "USB Cable"]query = "lap"matches = [name for name in products if query in name.lower()]print(matches) # ['Laptop Stand']$products = ['Desk Lamp', 'Laptop Stand', 'Office Chair', 'USB Cable'];$query = 'lap';$matches = array_values(array_filter($products,fn (string $name): bool => str_contains(strtolower($name), $query),));

For an exact name in a large sorted list, binary search works. For a real product catalog, use the database's full-text search or a dedicated search engine.

Searching for a record in a collection

The search functions built into most languages are linear search:

• Python: target in my_list, my_list.index(target)

• PHP: in_array($target, $array, true), array_search($target, $array, true)

They are correct and convenient. Just know they are O(n). Calling them inside a loop over another large list gives O(n × m) work, where m is the length of the outer list. When you need membership checks inside a loop, convert the data to a set in Python, or use array keys with isset() in PHP.

Looking up data in a database

SELECT id, name, emailFROM customersWHERE id = 42;

The database has two broad options:

• Full table scan (PostgreSQL calls it a sequential scan): read every row and check the condition. That is linear search over the table.

• Index lookup: an index is a separate sorted structure that maps column values to row locations. Most relational databases build indexes as B-trees, sorted trees where each node holds many keys. Finding a key repeatedly narrows the range, the same idea as binary search. The work grows logarithmically with the number of rows.

In PostgreSQL and MySQL, declaring a primary key creates an index on it automatically. Other columns you filter on often, such as email, need an index you create:

CREATE INDEX idx_customers_email ON customers (email);

The query planner is the part of the database that chooses how to run a query, and the result is the query execution plan. Use EXPLAIN to see it:

EXPLAIN SELECT id, name FROM customers WHERE email = 'asha@example.com';

The output shows whether the database will use an index or scan the table. Important points:

• An index exists only for the columns it was built on. Filtering by a column without an index means a full scan.

• The planner may choose a full scan even when an index exists, for example when the table is small or most rows match the condition. That can be the correct choice.

• WHERE name LIKE 'Lap%' (prefix match) can often use a B-tree index. WHERE name LIKE '%top%' (match anywhere) cannot use an ordinary B-tree index, because the sorted order is by the start of the value. Use a full-text index instead, or in PostgreSQL a trigram index.

• Do not load a whole table into your application and then loop over it. Let the database filter with WHERE, so it can use its indexes.

In Laravel, Customer::find(42) produces a query on the primary key, so the database uses the primary key index. Writing Customer::all()->firstWhere('id', 42) loads every customer into memory and runs a linear search in PHP.

Finding an element in a sorted dataset

When data is already sorted, use the language's binary search instead of writing your own. Python's bisect module provides one:

from bisect import bisect_leftdef contains_sorted(items, target):position = bisect_left(items, target)return position < len(items) and items[position] == targetsorted_skus = ["A100", "B205", "C310", "D420"]print(contains_sorted(sorted_skus, "C310")) # Trueprint(contains_sorted(sorted_skus, "C999")) # False

bisect_left returns the position where target would be inserted to keep the list sorted. If the element at that position equals the target, it is present. PHP has no built-in binary search over arrays, so use the binarySearch function from Section 4, or index the data by key.

8. Common Beginner Mistakes

Applying binary search to unsorted data

Binary search returns wrong answers on unsorted data without raising any error (see Section 4B). Sort first with sorted() in Python or sort() in PHP, or use linear search. If the data arrives from a database, add ORDER BY to the query. Do not assume the data is sorted.

Incorrect loop conditions

while low < high: # wrong for this version

With high = len(items) - 1, the search space includes high. Using < stops the loop while one element is still unchecked. Searching [7] for 7 then returns -1, because low == high == 0 and the loop never runs. Use while low <= high when high is the last valid index.

Off-by-one errors

high = len(items) # wrong for this version

len(items) is one past the last valid index. Searching [1, 2, 3] for 5 eventually computes mid = 3 and reads items[3], which raises IndexError in Python and produces an "undefined array key" warning in PHP. Pick one convention and keep it consistently:

• Inclusive: high = len(items) - 1, while low <= high, high = mid - 1. This is the convention used in this article.

• Half-open: high = len(items), while low < high, high = mid. This is the convention used by Exercise 5 and Python's bisect.

Mixing the two causes most binary search bugs.

Updating low and high incorrectly

low = mid # wrong in the inclusive version

Search [1, 3] for 3: mid = 0, items[0] = 1 < 3, so low = mid = 0. Nothing changes, and the loop runs forever. Because items[mid] has already been ruled out, always move past it: low = mid + 1 and high = mid - 1.

Also check the direction. If items[mid] < target, the target is to the right, so low moves up. Swapping the branches searches the wrong half.

Failing to handle an empty array

The functions in this article handle [] correctly: linear search's loop never runs, and binary search starts with high = -1, so its loop never runs either. Code that reads items[0] before checking the length, for example to look at the first element, crashes on an empty array. Always test the empty case (Section 9).

Ignoring duplicate values and missing targets

Duplicates: standard binary search returns a matching index, not necessarily the first one. In [2, 4, 4, 4, 9], searching for 4 returns index 2. If you need the first or last occurrence, use the modified version in Exercise 4.

Missing targets: check for the not-found signal before using the result.

index = linear_search(items, target)if index: # wrong: index 0 is falsy, and -1 is truthy...if index != -1: # correct...

The same trap exists in PHP's built-in array_search, which returns false when nothing is found and 0 for a match at the first position:

if (array_search($target, $items, true) !== false) {// found}

Assuming binary search is always faster

Binary search makes fewer comparisons on large sorted data. That does not make it the right choice for every workload:

• The data is unsorted and you search it once. Sorting costs O(n log n), more than one O(n) linear search.

• The data changes constantly. Keeping an array sorted means shifting elements on every insert.

• The collection is small. The difference is too small to matter, and simpler code is easier to maintain.

• You need exact-key lookups many times. A hash table gives O(1) on average.

• The data is in a database. The database's indexes do the searching. Your loop never sees most of the rows.

• You need partial text matches. Sorting does not help with "contains".

Choose based on the shape of the data and how often it is searched. If speed matters, measure your real workload rather than assuming.

9. Code Testing

Good tests cover the edges where search code usually breaks. For binary search with duplicates, test that the returned index holds the target, not that it equals one exact position, because any matching index is a correct answer.

Why each case matters:

• Empty array: catches code that reads an element before checking the length.

• Single element: catches a wrong loop condition (< instead of <=).

• Beginning and end: catch off-by-one errors at the boundaries.

• Missing, smaller than all, larger than all: confirm the loop ends cleanly with low > high and returns -1 instead of crashing or looping forever.

• Duplicates: confirm that linear search returns the first match, and that binary search returns some valid match.

Python tests

Save the functions from Section 4 in the same file, then add:

def run_tests():data = [3, 8, 12, 17, 23]duplicates = [2, 4, 4, 4, 9]for search in (linear_search, binary_search, binary_search_recursive):assert search([], 5) == -1assert search([7], 7) == 0assert search([7], 3) == -1assert search(data, 3) == 0assert search(data, 23) == 4assert search(data, 10) == -1assert search(data, 1) == -1assert search(data, 99) == -1index = search(duplicates, 4)assert index != -1 and duplicates[index] == 4assert linear_search(duplicates, 4) == 1print("All tests passed.")run_tests()

Expected output: All tests passed. If an assert fails, Python stops with an AssertionError that points to the failing line.

PHP tests

PHP disables assert() by default in many production configurations, so these tests use a small helper that always prints a result:

function check(string $label, bool $passed): void{echo ($passed ? 'PASS' : 'FAIL'), " - {$label}", PHP_EOL;}check('empty array', binarySearch([], 5) === -1 && linearSearch([], 5) === -1);check('single element found', binarySearch([7], 7) === 0 && linearSearch([7], 7) === 0);check('single element missing', binarySearch([7], 3) === -1 && linearSearch([7], 3) === -1);check('target at beginning', binarySearch([3, 8, 12, 17, 23], 3) === 0);check('target at end', binarySearch([3, 8, 12, 17, 23], 23) === 4);check('target missing', binarySearch([3, 8, 12, 17, 23], 10) === -1);$duplicates = [2, 4, 4, 4, 9];$index = binarySearch($duplicates, 4);check('duplicates (binary)', $index !== -1 && $duplicates[$index] === 4);check('duplicates (linear)', linearSearch($duplicates, 4) === 1);

Expected output: eight lines that each start with PASS. In a real project, write these as PHPUnit or Pest tests.

10. Practice Exercises

Try each exercise before reading the solutions in the next section.

Exercise 1: Count occurrences (beginner)

Write count_occurrences(items, target) that returns how many times target appears in an unsorted list.

• Sample input: items = [4, 2, 4, 7, 4], target = 4

• Expected output: 3

• Hint: Use linear search, but do not stop at the first match. Keep a counter.

Exercise 2: Find a customer's name by ID (beginner)

Write find_customer_name(customers, customer_id) that returns the customer's name, or None if no customer has that ID.

• Sample input:

  customers = [{"id": 101, "name": "Ravi"},{"id": 102, "name": "Asha"},{"id": 103, "name": "Mina"},]

  customer_id = 102

• Expected output: "Asha". For customer_id = 999, the output is None.

• Hint: Compare customer["id"] with the target, and return the name, not the whole dictionary.

Exercise 3: Count the steps of binary search (beginner to intermediate)

Modify binary search so it returns both the index and the number of comparisons with the middle element.

• Sample input: items = [3, 8, 12, 17, 23, 31, 42], target = 31

• Expected output: (5, 2). For target = 20, the output is (-1, 3).

• Hint: Increase a counter each time you compute mid and compare. Trace the example by hand first, using the table in Section 5.

Exercise 4: First occurrence in a sorted list (intermediate)

Write first_occurrence(items, target) that returns the index of the first occurrence of target in a sorted list, or -1 if it is absent. It must run in O(log n) time.

• Sample input: items = [1, 3, 3, 3, 5, 8], target = 3

• Expected output: 1. For target = 4, the output is -1.

• Hint: When you find a match, record it, but keep searching to the left. An earlier match may exist.

Exercise 5: Insert position (intermediate)

Write insert_position(items, target) that returns the index where target should be inserted to keep a sorted list sorted. If target already exists, return the index of its first occurrence.

• Sample input: items = [1, 3, 5, 6]

• Expected output:

  • target = 5 gives 2

  • target = 2 gives 1

  • target = 7 gives 4

  • target = 0 gives 0

• Hint: The answer can be len(items), one past the last index. Try the half-open convention: high = len(items) and while low < high.

Solutions

Solution 1

def count_occurrences(items, target):count = 0for value in items:if value == target:count += 1return count

Every element must be checked, because any element could be another match. Time O(n), space O(1). For an empty list, the result is 0.

Solution 2

def find_customer_name(customers, customer_id):for customer in customers:if customer["id"] == customer_id:return customer["name"]return None

This is linear search on a field of each record. If you look up customers by ID many times, build a dictionary once instead: {c["id"]: c["name"] for c in customers}.

Solution 3

def binary_search_steps(items, target):low = 0high = len(items) - 1steps = 0while low <= high:mid = (low + high) // 2steps += 1if items[mid] == target:return mid, stepsif items[mid] < target:low = mid + 1else:high = mid - 1return -1, steps

For 31: mid = 3 (17, go right), then mid = 5 (31, found), so the result is (5, 2). For 20, three comparisons empty the search space, as in Section 5.

Solution 4

def first_occurrence(items, target):low = 0high = len(items) - 1result = -1while low <= high:mid = (low + high) // 2if items[mid] == target:result = midhigh = mid - 1elif items[mid] < target:low = mid + 1else:high = mid - 1return result

The only change from standard binary search is the match branch: it saves mid and continues to the left instead of returning. Each step still halves the search space, so the time is O(log n). For [1, 3, 3, 3, 5, 8], the first match is at index 2, then the search finds index 1, and nothing further left is 3. The result is 1.

Solution 5

def insert_position(items, target):low = 0high = len(items)while low < high:mid = (low + high) // 2if items[mid] < target:low = mid + 1else:high = midreturn low

This uses the half-open convention: the candidate answers are positions low up to, but not including, high. Since the answer can be len(items), high starts there. When items[mid] >= target, mid might be the answer, so high = mid keeps it in range. The loop ends when low == high, and that position is the answer. This matches Python's bisect.bisect_left.

11. Key Takeaways

• A searching algorithm finds a target in a collection or reports that it is absent.

• Linear search checks elements one by one. It works on any data and costs O(n).

• Binary search checks the middle and discards half of the remaining elements each step. It costs O(log n), but only works on sorted data.

• low and high define the search space, and mid is the element being checked. Move past mid with mid + 1 and mid - 1.

• Use one boundary convention consistently. With inclusive high = len - 1, loop while low <= high.

• Always test an empty array, a single element, both ends, a missing target, and duplicates.

• Check the not-found signal explicitly. Index 0 is a valid result.

• For repeated exact-key lookups, a hash table (dict in Python, an associative array in PHP) is usually the best choice.

• In databases, indexes and query plans determine search performance. Use WHERE, appropriate indexes, and EXPLAIN, not application-side loops.

• The fastest algorithm in theory is not always the right choice. Consider sorting cost, data size, and how often the data changes.

12. Frequently Asked Questions

Is binary search always faster than linear search? No. On large sorted data searched many times, binary search makes far fewer comparisons. On unsorted data searched once, sorting first costs more than one linear search. On tiny lists, the difference rarely matters.

Why does binary search need sorted data? Discarding half of the data is safe only if every element on one side is known to be smaller and every element on the other side larger. Only sorted order guarantees that. On unsorted data, binary search returns wrong answers without any error.

Should I sort my data just so I can use binary search? Only if you will search it many times. Sorting costs O(n log n) once, then each search costs O(log n). For a single search, linear search is cheaper. For many exact-key lookups, a hash table is usually simpler and faster.

Do Python's in and PHP's in_array use binary search? No. On lists and arrays, both are linear searches, because they cannot assume the data is sorted. Python's in on a set or dict, and PHP's isset($array[$key]), are hash lookups with O(1) average time.

Why return -1 instead of None or false? -1 is never a valid index, so it clearly means "not found", and it keeps the return type an integer in both languages. Python's built-in list.index() raises a ValueError instead, and PHP's array_search() returns false. Any of these choices works if you check for it explicitly.

Should I use the iterative or recursive version of binary search? Prefer the iterative version in real code: it uses constant memory and is easier to debug. Study the recursive version to understand divide and conquer. Both take O(log n) time.

Can binary search work with strings? Yes, if the strings are sorted with the same comparison used during the search. Case matters: in Python, "apple" < "Banana" is False, because uppercase letters sort before lowercase. Normalize the case of both the data and the target if your search should ignore case.

Is a hash table a searching algorithm? A hash table is a data structure, a way of organizing data, that makes searching by exact key very fast. It computes where a key is stored instead of scanning or halving. It does not support "find the nearest value" or range queries, which is where sorted data and binary search still matter.

13. Further Learning

Study these next, roughly in this order:

1. Big-O notation in depth. Analyzing loops, nested loops, and recursion, and the meaning of O(n log n) and O(n²).

2. Sorting algorithms. Insertion sort, merge sort, and quicksort, and how much sorting costs before binary search can be used.

3. Binary search variations. First and last occurrence, insert position, searching a rotated sorted array, and binary search on the answer, which searches over a range of possible answers rather than over an array.

4. Hash tables. How hashing works, what a collision is, and why lookups are O(1) on average but not guaranteed.

5. Trees and B-trees. Binary search trees, balanced trees, and how B-trees power database indexes.

6. Database indexing. Composite indexes, reading EXPLAIN output, and full-text search.

7. Graph search. Breadth-first search and depth-first search, which apply the idea of searching to networks of connected data.