Searching in DSA
Searching means finding a particular element in a collection of data.
For example:
Array: 10 25 30 45 60 75 Search: 45
The answer is:
45 found at index 3
Searching is one of the most fundamental DSA operations.
The two most important searching algorithms are:
- Linear Search
- Binary Search
1. Why Do We Need Searching?
Suppose you have:
10 25 30 45 60 75
You want to find:
60
A simple approach is to check every element:
10 ❌ 25 ❌ 30 ❌ 45 ❌ 60 ✅
This is Linear Search.
But because the array is sorted, we can do something much faster.
We can check the middle:
10 25 30 | 45 | 60 75 ↑
Then decide whether to search left or right.
This is Binary Search.
2. Types of Searching
The main searching techniques in basic DSA are:
Searching │ ├── Linear Search │ └── Binary Search
There are also advanced searching techniques:
Hashing BST Trie Graph Search
You have already learned some of these.
3. Linear Search
Linear Search is the simplest searching algorithm.
The idea:
Check each element one by one until the target is found.
Example:
Array: 10 25 30 45 60 Target = 45
Start from index 0:
10 == 45 ❌
Next:
25 == 45 ❌
Next:
30 == 45 ❌
Next:
45 == 45 ✅
Found at index:
3
4. Linear Search Code
int linearSearch(vector<int>& arr, int target) { for (int i = 0; i < arr.size(); i++) { if (arr[i] == target) { return i; } } return -1; }
Example:
#include <iostream> #include <vector> using namespace std; int linearSearch(vector<int>& arr, int target) { for (int i = 0; i < arr.size(); i++) { if (arr[i] == target) { return i; } } return -1; } int main() { vector<int> arr = {10, 25, 30, 45, 60}; int target = 45; int index = linearSearch(arr, target); if (index != -1) cout << "Found at index " << index; else cout << "Not found"; return 0; }
Output:
Found at index 3
5. Linear Search Complexity
Suppose:
n = number of elements
Best Case
Target is the first element:
10 20 30 40 ↑
Only one comparison.
O(1)
Worst Case
Target is the last element:
10 20 30 40 ↑
Or target doesn't exist.
We check all n elements:
O(n)
Average Case
Approximately:
O(n)
Space:
O(1)
6. When Should We Use Linear Search?
Linear Search is useful when:
- Data is unsorted.
- Dataset is small.
- You only need to search once.
- Simplicity is important.
Example:
50 12 89 3 41
This isn't sorted.
You can simply use Linear Search.
7. Binary Search
Now we come to one of the most important searching algorithms.
Binary Search repeatedly divides the search space into two halves.
But there is one very important condition:
The data must be sorted.
Example:
10 20 30 40 50 60 70
Target:
60
Instead of checking every element, check the middle.
8. Binary Search Example
Array:
10 20 30 40 50 60 70
Target:
60
Set:
left = 0 right = 6
Calculate middle:
mid = left + (right - left) / 2
So:
mid = 3
Element:
arr[3] = 40
Compare:
60 > 40
Therefore, target must be on the right side.
Ignore:
10 20 30 40
Search:
50 60 70
9. Second Step
Now:
left = 4 right = 6
Middle:
mid = 5
Element:
arr[5] = 60
Target:
60 == 60
Found!
index = 5
10. Binary Search Visualization
10 20 30 40 50 60 70 ↑ mid 60 > 40 ↓ Ignore left half 50 60 70 ↑ mid 60 == 60 ↓ FOUND
Notice that we didn't inspect:
10 20 30
at all.
That's the power of Binary Search.
11. Binary Search Logic
There are three possibilities.
Case 1 — Found
arr[mid] == target
Return mid.
Case 2 — Target is greater
arr[mid] < target
Search right:
left = mid + 1;
Case 3 — Target is smaller
arr[mid] > target
Search left:
right = mid - 1;
12. Binary Search Code — Iterative
int binarySearch(vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { return mid; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return -1; }
Example:
vector<int> arr = { 10, 20, 30, 40, 50, 60, 70 }; cout << binarySearch(arr, 60);
Output:
5
13. Why left + (right-left)/2?
You may see:
int mid = (left + right) / 2;
This usually works.
But for very large integer indices, left + right can overflow.
Safer:
int mid = left + (right - left) / 2;
This is the standard form you should use.
14. Binary Search Complexity
Every step removes approximately half of the remaining elements.
Suppose:
n = 16
Search sizes:
16 ↓ 8 ↓ 4 ↓ 2 ↓ 1
Number of steps:
log₂(16) = 4
Therefore:
Best Case: O(1) Average Case: O(log n) Worst Case: O(log n)
Space for iterative Binary Search:
O(1)
This is much faster than Linear Search for large sorted arrays.
15. Linear vs Binary Search
| Feature | Linear Search | Binary Search |
|---|---|---|
| Data must be sorted? | No | Yes |
| Best | O(1) | O(1) |
| Average | O(n) | O(log n) |
| Worst | O(n) | O(log n) |
| Space | O(1) | O(1) |
| Simple | Very simple | Slightly more complex |
16. Recursive Binary Search
Binary Search can also be implemented using recursion.
int binarySearch( vector<int>& arr, int left, int right, int target ) { if (left > right) return -1; int mid = left + (right - left) / 2; if (arr[mid] == target) return mid; if (arr[mid] < target) return binarySearch( arr, mid + 1, right, target ); return binarySearch( arr, left, mid - 1, target ); }
Call:
int index = binarySearch( arr, 0, arr.size() - 1, target );
Time:
O(log n)
Recursive auxiliary space:
O(log n)
because of the function call stack.
17. Binary Search on Descending Arrays
Binary Search doesn't require ascending order specifically.
It can also work on:
90 80 70 60 50 40 30
But your comparison logic must account for the descending order.
For ascending:
if (arr[mid] < target) left = mid + 1;
For descending, the direction is reversed.
18. First Occurrence
Now we move into an important Binary Search pattern.
Suppose:
arr = {1, 2, 2, 2, 3, 4}
Target:
2
There are three occurrences:
1 2 2 2 3 4 ↑ ↑ ↑
We may want the first occurrence.
Answer:
index = 1
Normal Binary Search may return any one of the 2s.
So we modify the algorithm.
int firstOccurrence(vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; int answer = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { answer = mid; // Continue searching left right = mid - 1; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return answer; }
19. Last Occurrence
For:
1 2 2 2 3 4
Target:
2
Last occurrence:
index = 3
Code:
int lastOccurrence(vector<int>& arr, int target) { int left = 0; int right = arr.size() - 1; int answer = -1; while (left <= right) { int mid = left + (right - left) / 2; if (arr[mid] == target) { answer = mid; // Continue searching right left = mid + 1; } else if (arr[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return answer; }
20. Count Occurrences
Once we know:
first occurrence last occurrence
we can calculate:
count = last - first + 1
Example:
1 2 2 2 3 4
First:
1
Last:
3
Therefore:
count = 3 - 1 + 1 = 3
21. Lower Bound
Another extremely important Binary Search concept is:
Lower Bound = first position where
arr[i] >= target.
Example:
1 3 3 5 7 9
Target:
4
First value >= 4:
5
Index:
3
In C++:
lower_bound(arr.begin(), arr.end(), target);
22. Upper Bound
Upper Bound = first position where arr[i] > target.
Example:
1 3 3 5 7 9
Target:
3
First value greater than 3:
5
Index:
3
C++:
upper_bound(arr.begin(), arr.end(), target);
23. lower_bound and upper_bound
For:
1 2 2 2 4 5
Target:
2
We get:
lower_bound → index 1 upper_bound → index 4
Therefore:
number of occurrences = upper_bound - lower_bound = 4 - 1 = 3
This is a very useful competitive-programming technique.
24. Binary Search on Answer
This is a very important advanced pattern.
Sometimes we aren't searching for an element.
Instead, we're searching for the minimum or maximum possible answer.
Example:
Find the minimum speed required to finish a task within a given time.
The possible answers might be:
1 2 3 4 5 6 7 8 9 10
There may be a condition:
speed < 5 → ❌ impossible speed >= 5 → ✅ possible
So:
1 2 3 4 | 5 6 7 8 9 10 ↑ first valid
This is called:
Binary Search on Answer
It is extremely common in advanced DSA problems.
25. Examples of Binary Search on Answer
Common problems include:
- Minimum eating speed
- Minimum capacity
- Allocate books
- Split array largest sum
- Aggressive cows
- Minimum days to make bouquets
- Maximum minimum distance
- Ship packages within D days
The pattern is:
Possible answer range ↓ Check whether answer works ↓ If works → search smaller/larger ↓ Binary Search
26. Searching in a Rotated Sorted Array
Consider:
1 2 3 4 5 6 7
Rotate it:
4 5 6 7 1 2 3
It is no longer completely sorted.
But it contains two sorted sections:
4 5 6 7 | 1 2 3
A modified Binary Search can still search in:
O(log n)
This is a common interview problem.
27. Search in a 2D Matrix
Suppose:
1 3 5 7 10 11 16 20 23 30 34 60
We may need to search for:
16
Depending on the matrix properties, we can use Binary Search or other efficient approaches.
This connects Binary Search with:
Arrays + 2D arrays + searching.
28. Searching and Previous DSA Topics
Searching connects strongly with topics you've already learned.
Arrays
Array ↓ Linear Search
Sorting
Sort ↓ Binary Search
BST
BST ↓ Search using tree ordering
Hashing
Hash Table ↓ Average O(1) lookup
Graphs
Graph ↓ BFS / DFS ↓ Search for reachable nodes
29. Searching Methods Comparison
| Method | Data Requirement | Average Time |
|---|---|---|
| Linear Search | Any data | O(n) |
| Binary Search | Sorted data | O(log n) |
| Hash Table | Hashable keys | O(1) average |
| BST | Ordered tree | O(log n) average if balanced |
| BFS | Graph | O(V + E) |
| DFS | Graph | O(V + E) |
| Trie | String/prefix data | O(L) |
Here:
L = length of the string
30. Important C++ STL Searching Functions
find()
For a vector:
auto it = find(arr.begin(), arr.end(), target);
Complexity:
O(n)
binary_search()
For a sorted range:
bool found = binary_search( arr.begin(), arr.end(), target );
Returns:
true / false
lower_bound()
Returns first position:
>= target
upper_bound()
Returns first position:
> target
These require the range to be sorted for their standard logarithmic behavior.
31. Most Important Interview Patterns
When you see a searching problem, ask:
Question 1
Is the data sorted?
If no:
Linear Search
If yes:
Binary Search may be possible
Question 2
Can I eliminate half of the search space?
If yes:
Binary Search
Question 3
Am I looking for the first/last valid position?
Think:
Lower Bound Upper Bound Binary Search
Question 4
Am I searching for an answer rather than an element?
Think:
Binary Search on Answer
32. Complexity Summary
Linear Search Best → O(1) Average → O(n) Worst → O(n) Space → O(1)
Binary Search Best → O(1) Average → O(log n) Worst → O(log n) Space → O(1) iterative
Final Mental Model
SEARCHING │ ┌─────────┴─────────┐ ↓ ↓ Linear Search Binary Search │ │ Any array Sorted data │ │ Check one by one Divide by 2 │ │ O(n) O(log n)
And the most important Binary Search patterns:
Binary Search │ ├── Find exact element ├── First occurrence ├── Last occurrence ├── Lower bound ├── Upper bound ├── Rotated sorted array └── Binary Search on Answer