Ugenz Academy/Tutorial

Searching

13 min read2,447 words

Reading progress

Keep learning

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:

  1. Linear Search
  2. 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

FeatureLinear SearchBinary Search
Data must be sorted?NoYes
BestO(1)O(1)
AverageO(n)O(log n)
WorstO(n)O(log n)
SpaceO(1)O(1)
SimpleVery simpleSlightly 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

MethodData RequirementAverage Time
Linear SearchAny dataO(n)
Binary SearchSorted dataO(log n)
Hash TableHashable keysO(1) average
BSTOrdered treeO(log n) average if balanced
BFSGraphO(V + E)
DFSGraphO(V + E)
TrieString/prefix dataO(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

Keep learning. Keep building. Keep growing.

© 2026 Ugenz Academy