Introduction

When a MATLAB vector is already sorted, a plain find call often leaves performance on the table. find scans elements linearly, while sorted data allows logarithmic-time strategies such as binary search.

Why find Is Not Ideal for Sorted Data

A call such as idx = find(x == target, 1); works, but it does not exploit the fact that x is ordered. For a large vector, that means worst-case linear work. If you only need one matching index, or the first element greater than or equal to a target, a binary-search approach is usually faster.

This matters most when x is large and you repeat the query many times. The cost of a single scan may be acceptable, but thousands of scans over the same sorted vector add up quickly.

Exact Match with Binary Search

The core idea is simple: compare the target with the middle element, then discard half of the remaining search interval on each step.

1function idx = binaryFindSorted(x, target)
2    left = 1;
3    right = numel(x);
4    idx = 0;
5
6    while left <= right
7        mid = floor((left + right) / 2);
8
9        if x(mid) == target
10            idx = mid;
11            return;
12        elseif x(mid) < target
13            left = mid + 1;
14        else
15            right = mid - 1;
16        end
17    end
18end

x = [3 8 12 19 27 31 44 55];
idx = binaryFindSorted(x, 27)

If the value is present, idx contains one matching position. If not, the function returns 0, which is a convenient sentinel in MATLAB because valid indices start at 1.

Finding the First Position in a Sorted Range

A frequent requirement is not exact equality, but the first position where a sorted vector reaches or exceeds a threshold. This is often called a lower-bound search.

1function idx = lowerBoundSorted(x, target)
2    left = 1;
3    right = numel(x);
4    idx = numel(x) + 1;
5
6    while left <= right
7        mid = floor((left + right) / 2);
8
9        if x(mid) >= target
10            idx = mid;
11            right = mid - 1;
12        else
13            left = mid + 1;
14        end
15    end
16
17    if idx > numel(x)
18        idx = 0;
19    end
20end

x = [10 15 20 20 35 40];
idx = lowerBoundSorted(x, 20)

For range queries, this is usually more useful than find, because it gives the first qualifying index directly instead of scanning from the start.

When This Optimization Helps

Binary search helps only if the data is sorted in the direction you expect. It is most useful when:

• the vector is large,
• you perform many lookups,
• you need one index rather than all matches,
• or you need boundary positions such as the first value greater than or equal to a threshold.

If you need every matching index in a vector with many duplicates, find may still be the better tool because the output itself can be large. The optimization target is search cost, not the cost of returning many results.

Practical Advice for MATLAB Code

Keep the search helper small and well-tested. If you call it many times, store it in its own file and benchmark with timeit. MATLAB performance can vary with vector size and workload shape, so measure the exact operation you care about instead of assuming a theoretical improvement will dominate every case.

Also remember that a sorted vector is a contract. If later code appends unsorted values, a binary search silently becomes wrong. That is more dangerous than slow code because the result can look plausible while being incorrect.

Common Pitfalls

• Using binary search on data that is not fully sorted produces wrong indices, not just slower performance.
• Expecting one exact-match function to return every duplicate index misunderstands the tradeoff; binary search normally finds one position or a boundary.
• Returning 0 for not found is convenient in MATLAB, but downstream code must check for it before indexing.
• Benchmarking with tiny vectors can hide the benefit because function-call overhead dominates the search cost.
• Comparing floating-point values with == can miss near-equal results, so tolerance-based logic may be needed for numeric data.

Summary

• 'find is linear and does not exploit sorted input.'
• Binary search reduces exact-match and boundary queries to logarithmic time.
• A lower-bound helper is often more useful than searching for exact equality.
• The optimization is valuable for large vectors and repeated lookups.
• Sortedness is a hard requirement, so validate that assumption before replacing find.