Searching in Arrays - Step by Step Understanding

What is Searching?

Searching means:

• Checking if a value exists in an array
• If it exists, finding its position (index)

---

Problem Example

arr = [10, 20, 30, 40]
target = 30

We want to find:

• Does 30 exist? → Yes
• At what index? → 2

---

Method 1: Linear Search (linear_search)

When the array is not sorted, we check one by one.

def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

How It Works (Step by Step)

arr = [10, 20, 30]
target = 30

Steps:

• i = 0 → 10 != 30
• i = 1 → 20 != 30
• i = 2 → 30 == target → return 2

Time Complexity

O(n) → worst case checks all elements

When to Use Linear Search?

• Array is unsorted
• Small data size
• Only one search needed

Problem with Linear Search

If the array is very large:

• It becomes slow
• We check many unnecessary elements

---

Method 2: Binary Search (sorted_array_logic + middle_index_logic)

Works only when the array is sorted.

arr = [10, 20, 30, 40, 50]

Core Idea

Instead of checking all elements:

1. Check the middle element
2. Decide whether to go left or right

Sorted order (sorted_array_logic) tells you which half can still contain the target. Choosing mid and updating left / right repeatedly is middle_index_logic.

Middle Index

mid = (left + right) // 2

(Optional safety on huge integers: mid = left + (right - left) // 2.)

Binary Search Code

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid

        elif target < arr[mid]:
            right = mid - 1

        else:
            left = mid + 1

    return -1

Example

arr = [10, 20, 30, 40, 50]
target = 40

Steps:

• left = 0, right = 4
• mid = 2 → value = 30
• 30 < 40 → go right
• left = 3
• mid = 3 → value = 40 → found

Why Binary Search Is Fast

Each step reduces search space by half.

Time Complexity

O(log n)

Important Condition

Binary search works only if:

• Array is sorted

---

Rotated sorted array - rotated_array_search

Sometimes the array was sorted, then rotated at an unknown pivot.

Example (originally sorted ascending, then rotated):

nums = [4, 5, 6, 7, 0, 1, 2]

It is not globally sorted anymore, but one half between left and right is always sorted. Binary search can still run in O(log n) by deciding which sorted half contains target.

Idea

At each mid:

1. If nums[mid] == target → found
2. If the left segment nums[left … mid] is sorted (nums[left] <= nums[mid]):
   • If target lies inside that sorted range → search left
   • Else → search right
3. Else the right segment nums[mid … right] is sorted:
   • If target lies inside that sorted range → search right
   • Else → search left

Code (distinct values)

def search_rotated(nums, target):
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

Example

nums = [4, 5, 6, 7, 0, 1, 2]
print(search_rotated(nums, 0))  # 4

Note on duplicates

If nums can contain many equal values, the “which half is sorted?” test can become ambiguous; interview versions often assume distinct elements (or you add extra tie-breaking rules).

---

Common Mistakes (Binary Search)

• Using binary search on an unsorted array
• Incorrect left / right updates
• Wrong loop condition

---

Method 3: Hashing (Fast Lookup)

If we need very fast searching multiple times:

arr = [10, 20, 30]

lookup = {}
for i in range(len(arr)):
    lookup[arr[i]] = i

print(lookup[30])  # Output: 2

Time Complexity

O(1) average lookup after building the map

When to Use Hashing?

• Multiple searches
• Fast lookup required
• Extra memory is allowed

---

Method 4: Using Set (Existence Check)

arr = [10, 20, 30]

s = set(arr)

print(30 in s)  # True

Use Case

Only need to check presence - no index needed.

---

Method 5: Two Pointers (For Sorted Arrays)

Used in problems like:

Find two numbers whose sum = target.

arr = [1, 2, 3, 4, 5]
target = 6

left = 0
right = len(arr) - 1

while left < right:
    ss = arr[left] + arr[right]

    if ss == target:
        print("Found")
        break
    elif ss < target:
        left += 1
    else:
        right -= 1

Why It Works

Uses sorted order - moves pointers based on comparison.

Time Complexity

O(n)

(This pattern is explored in depth on the Two Pointers lesson.)

---

Comparison Table

Method	Condition	Time	Space
Linear Search	Any array	O(n)	O(1)
Binary Search	Sorted array	O(log n)	O(1)
Rotated binary	Rotated sorted (distinct)	O(log n)	O(1)
Hashing	Extra memory allowed	O(1) avg*	O(n)
Set	Existence check	O(1) avg*	O(n)
Two Pointers	Sorted array	O(n)	O(1)

*Build cost for hash/set applies once; lookups are average-case.

---

Key Understanding

Choosing the correct method depends on:

• Is the array sorted?
• How many searches?
• Is extra memory allowed?

---

Practice Questions

• Implement linear search
• Implement binary search
• Search a rotated sorted array in O(log n)
• Find if element exists using set
• Solve pair sum using two pointers

---

Final Thought

Searching is one of the most important concepts.

Always ask:

• Can I do better than O(n)?
• Is the array sorted?
• Can I use extra memory?

Continue here:

/resources/arrays/two-pointers