Searching Problems

You walk into a huge library to find one book.

Two ways to search:

1. You start from the first shelf and check every book one by one…
2. Or you go to the middle shelf, check the category, and instantly eliminate half the library…

Both methods work.
But one is smart, the other is slow.

That’s exactly what searching in arrays is about.

Linear Search (The “Check Everything” Method)

Sequential Search

You check each element one by one until you find the target.

Technical Example:

• Input: [10, 5, 8, 20], target = 8
• Output: 2

Real-Life Example:
Searching your name in an unsorted attendance list.

Time Complexity: O(n)

Binary Search (The “Think Smart” Method)

Divide and Conquer

Instead of checking everything, you:

1. Go to the middle element
2. Compare with target
3. Eliminate half of the array
4. Repeat

But there’s a rule:
Array must be sorted

Code Example:

Technical Example:

• Input: [1, 3, 5, 7, 9], target = 7
• Output: 3

Time Complexity: O(log n)

Linear vs Binary Search (The Real Difference)

When to Use What?

• Use Linear Search when:
  • Array is unsorted
  • Size is small
• Use Binary Search when:
  • Array is sorted
  • Need fast performance

Interview Twists on Searching

Interviewers rarely ask direct questions. Instead, they twist them:

• “Find first occurrence of element”
• “Find last occurrence”
• “Find element in rotated sorted array”
• “Count occurrences using binary search”

Same concept, different thinking.

Searching is not about finding
It's about how efficiently you eliminate possibilities.

• Linear Search = Effort
• Binary Search = Strategy