Definition
- Linear search – examines elements one at a time from the start until the target is found or the collection is exhausted, giving O(n) time.
- Binary search – requires sorted data and halves the range each step by comparing the middle element, giving O(log n) time.
- Precondition trade-off – binary search is far faster but pays the upfront cost of keeping data sorted.
- Amortised cost – sorting once and searching many times amortises the O(n log n) sort cost across all lookups.
- Access pattern – linear search works on linked lists and streams; binary search requires random access like arrays.
Suppose you are looking for Rajesh's account in a stack of files at the National Bank of India. Linear search is reading every file from the top of the pile one by one until you hit his, which is simple and works even if the pile is a mess, but slow if the pile is huge. Binary search is like using a sorted filing cabinet: you jump to the middle drawer, decide whether Rajesh is before or after, and keep halving. It is lightning fast, but only works because someone kept the cabinet sorted.
Understanding the Concepts
What is linear search?
Linear search is the simplest possible search algorithm. It loops from index zero and compares each element to the target. If a match is found, it returns the index. If it reaches the end without a match, the target is absent. It makes no assumptions about the order of the data.
package com.bank.search;
public class LinearSearch {
public static int search(long[] accounts, long target) {
for (int i = 0; i < accounts.length; i++) {
if (accounts[i] == target) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
long[] accounts = {1080, 1001, 1050, 1025, 1100}; // unsorted is fine
int idx = search(accounts, 1050);
System.out.println("Found account 1050 at index: " + idx);
}
}
Found account 1050 at index: 2
What is binary search?
Binary search works on sorted data. It maintains two pointers that bound the active range and examines the middle element. If the target is smaller, it discards the right half; if larger, it discards the left half. Each step halves the range.
package com.bank.search;
public class BinarySearch {
public static int search(long[] sortedAccounts, long target) {
int low = 0, high = sortedAccounts.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (sortedAccounts[mid] == target) return mid;
if (sortedAccounts[mid] < target) low = mid + 1;
else high = mid - 1;
}
return -1;
}
public static void main(String[] args) {
long[] sorted = {1001, 1025, 1050, 1080, 1100}; // must be sorted
int idx = search(sorted, 1050);
System.out.println("Found account 1050 at index: " + idx);
}
}
Found account 1050 at index: 2
How do they compare side by side?
| Property | Linear Search | Binary Search |
|---|---|---|
| Time complexity | O(n) | O(log n) |
| Precondition | None | Data must be sorted |
| Data structures | Any (array, list, stream) | Random-access (array) |
| Comparisons for n = 1,000,000 | Up to 1,000,000 | About 20 |
| Space | O(1) | O(1) iterative |
| Stability concern | N/A | N/A |
| Best for | Small data, one-off search, unsorted data | Large sorted data, repeated lookups |
package com.bank.search;
import java.util.Arrays;
public class ComparisonDemo {
public static void main(String[] args) {
int n = 1_000_000;
long[] arr = new long[n];
for (int i = 0; i < n; i++) arr[i] = i * 2L;
long target = 999_998L;
// Linear search
long start = System.nanoTime();
int linIdx = -1;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == target) { linIdx = i; break; }
}
long linTime = System.nanoTime() - start;
// Binary search
start = System.nanoTime();
int binIdx = Arrays.binarySearch(arr, target);
long binTime = System.nanoTime() - start;
System.out.println("Linear: index=" + linIdx + " time=" + linTime + "ns");
System.out.println("Binary: index=" + binIdx + " time=" + binTime + "ns");
}
}
Linear: index=499999 time=1250000ns
Binary: index=499999 time=800ns
When is linear search actually better?
Linear search wins when the data is unsorted and you search it only once. Sorting costs O(n log n), so if you sort and then binary search, the total cost is O(n log n) + O(log n), which exceeds the O(n) of a single linear scan. Linear search also works on linked lists and streams where you cannot jump to the middle.
package com.bank.search;
public class OneOffSearch {
public static void main(String[] args) {
// Unsorted transactions: one-off search
int[] unsorted = {500, 120, 800, 350, 200};
int target = 350;
// Linear: O(n) total
for (int i = 0; i < unsorted.length; i++) {
if (unsorted[i] == target) {
System.out.println("Linear found at " + i);
break;
}
}
// Binary: would need sort first, O(n log n) + O(log n)
// Not worth it for a single query
}
}
Linear found at 3
When is binary search the clear winner?
Binary search wins when you search the same sorted collection many times. You sort once and enjoy O(log n) lookups forever. This is exactly why databases maintain sorted indexes: the index is sorted once (or incrementally maintained), and every query benefits from logarithmic lookup.
package com.bank.search;
import java.util.Arrays;
public class RepeatedSearch {
public static void main(String[] args) {
long[] accounts = new long[100_000];
for (int i = 0; i < accounts.length; i++) accounts[i] = 1000L + i;
Arrays.sort(accounts); // sort once
// Search 10,000 times
long start = System.nanoTime();
for (int q = 0; q < 10_000; q++) {
Arrays.binarySearch(accounts, 50_000L + q);
}
long elapsed = System.nanoTime() - start;
System.out.println("10,000 binary searches: " + elapsed / 1_000_000 + " ms");
}
}
10,000 binary searches: 2 ms
What about HashMap as an alternative?
When you need only existence checks or key-value lookups and do not need ordering or range queries, a HashMap gives O(1) average-case time, beating both linear and binary search. But it uses more memory and does not support "find all accounts between 1000 and 2000" the way a sorted array with binary search does.
package com.bank.search;
import java.util.HashMap;
import java.util.Map;
public class HashMapAlternative {
public static void main(String[] args) {
Map<Long, String> accountMap = new HashMap<>();
accountMap.put(1001L, "Rajesh Savings");
accountMap.put(1025L, "Priya Current");
accountMap.put(1050L, "Rajesh Loan");
// O(1) average lookup
String name = accountMap.get(1025L);
System.out.println("Account 1025: " + name);
// But no range query support
System.out.println("Range query? Not with HashMap.");
}
}
Account 1025: Priya Current
Range query? Not with HashMap.
What are the edge cases and pitfalls?
The biggest pitfall is applying binary search to unsorted data, which gives wrong results silently. Another edge case is an empty array, where both algorithms correctly return not-found. For linear search, the worst case is the target at the very end or absent. For binary search, the worst case is still only O(log n).
package com.bank.search;
import java.util.Arrays;
public class Pitfalls {
public static void main(String[] args) {
int[] unsorted = {50, 20, 80, 10, 40};
// Binary search on unsorted: WRONG result
int result = Arrays.binarySearch(unsorted, 40);
System.out.println("Binary on unsorted: " + result + " (unreliable)");
// Empty array: both return -1
int[] empty = {};
System.out.println("Linear on empty: -1");
System.out.println("Binary on empty: " + Arrays.binarySearch(empty, 5));
}
}
Binary on unsorted: -3 (unreliable)
Linear on empty: -1
Binary on empty: -1
How do you choose in a real banking system?
The choice depends on the access pattern:
- Small data or one-off search on unsorted data: use linear search.
- Large sorted data queried repeatedly: sort once, then binary search.
- Frequent key-value lookups without ordering: use
HashMap. - Frequent lookups with range queries and ordering: use
TreeMap(balanced BST with binary search inside).
package com.bank.search;
import java.util.TreeMap;
public class TreeMapRangeQuery {
public static void main(String[] args) {
TreeMap<Long, String> accounts = new TreeMap<>();
accounts.put(1001L, "Rajesh");
accounts.put(1025L, "Priya");
accounts.put(1050L, "Pankaj");
accounts.put(1080L, "Neha");
accounts.put(1100L, "Amit");
// Range query: accounts between 1020 and 1060
System.out.println("Range [1020, 1060]: "
+ accounts.subMap(1020L, true, 1060L, true));
}
}
Range [1020, 1060]: {1025=Priya, 1050=Pankaj}
What should a senior engineer know?
A senior engineer matches the algorithm to the access pattern rather than always reaching for the fastest Big-O. They understand that binary search needs sorted data and that maintaining sort order has a cost. They also know that in databases, B-tree indexes are binary search applied to sorted pages, which is why creating an index speeds up queries but slows down writes. The real interview test is knowing when to use each tool, not just how to implement them.
Visual Overview
Linear Search: ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 10│ 25│ 30│ 50│ 60│ 75│ 80│ 90│ target = 75 └───┴───┴───┴───┴───┴───┴───┴───┘ [1] [2] [3] [4] [5] [6] check check check check check FOUND 6 comparisons Binary Search: ┌───┬───┬───┬───┬───┬───┬───┬───┐ │ 10│ 25│ 30│ 50│ 60│ 75│ 80│ 90│ target = 75 └───┴───┴───┴───┴───┴───┴───┴───┘ Step 1: mid=3 (50) < 75 → go right Step 2: mid=5 (75) == 75 → FOUND 2 comparisons
Decision Guide:
┌────────────────────────┐
│ Is data sorted? │
└──────┬────────┬────────┘
│ yes │ no
▼ ▼
┌──────────┐ ┌──────────────┐
│ Repeated │ │ Linear scan │
│ queries? │ │ O(n) │
└───┬──┬───┘ └──────────────┘
yes│ │no
▼ ▼
┌────────┐ ┌──────────────────┐
│ Binary │ │ Sort once + binary│
│ search │ │ if worth the cost │
└────────┘ └──────────────────┘
Key Takeaway
Linear search and binary search solve the same problem of finding a target but make opposite trade-offs. Linear search checks elements one at a time from the start and works on any data, sorted or not, in O(n) time. Binary search requires sorted data and halves the range each step, running in O(log n) time. For one million elements, linear search may need one million comparisons while binary search needs only about twenty.
The subtlety is the amortised cost. Binary search is faster per query, but keeping data sorted costs O(n log n). If you search a collection only once, a linear scan is cheaper overall. If you search the same collection many times, you sort once and enjoy logarithmic lookups forever, which is exactly why databases maintain sorted indexes.
In a banking system at the National Bank of India, the choice depends on the access pattern. For a one-off audit of unsorted transaction records, linear scan is the right tool. For the sorted account ledger queried thousands of times per second, binary search is indispensable. And when only key-value lookups are needed without ordering, a HashMap with O(1) average time often beats both.
The senior-level answer is that choosing correctly among linear search, binary search, HashMap, and TreeMap based on data characteristics and access patterns is what the interviewer is really testing.
Remember one sentence: linear search is O(n) on anything, binary search is O(log n) on sorted data, and matching the tool to the access pattern is the real skill.
---