DSA-Iterative-Search

Programmer's Picnic — Binary Search (Iterative)

Short, practical lesson — iterative binary search with dry-run and code.

Self-study • Beginner → Intermediate

Date: [Replace with date]
Time: [Replace with time & timezone]

Start Lesson See Agenda Materials & Code

What is Binary Search?

Binary search finds a target value in a sorted array by repeatedly dividing the search interval in half. Each step cuts the remaining search space roughly in half — so it’s fast.

Agenda

1. Idea & intuition
2. Pseudocode & iterative implementation
3. Dry-run on an example
4. Run the code (Python) & small exercise
5. MCQ lightning quiz

Intuition (short)

Given a sorted list, check the middle element. If it equals the target — done. If target is smaller, repeat on left half. If larger, repeat on right half. Keep narrowing until you find the target or the segment is empty.

Pseudocode (Iterative)

function binary_search_iterative(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid        # found: return index
        elif arr[mid] < target:
            left = mid + 1   # search right half
        else:
            right = mid - 1  # search left half
    return -1                 # not found
  

Python — Iterative Binary Search

# Iterative binary search (assumes arr is sorted ascending)
def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# quick demo
a = [1, 3, 4, 6, 8, 9, 12, 15]
print("Array:", a)
t = 8
print("Search", t, "-> index:", binary_search_iterative(a, t))  # should print index 4
  

Tip: The array must be sorted. If not sorted, sort it or use a different algorithm (e.g., linear search).

Dry-run example

Array: [1, 3, 4, 6, 8, 9, 12, 15], target = 8

1. left=0, right=7 → mid=3 → arr[3]=6 (6 < 8) → search right half → left=4
2. left=4, right=7 → mid=5 → arr[5]=9 (9 > 8) → search left half → right=4
3. left=4, right=4 → mid=4 → arr[4]=8 → found at index 4

Complexity & Notes

• Time complexity: O(log n) (each step halves the search space)
• Space complexity: O(1) (iterative, constant extra memory)
• Requirement: data must be sorted. For unsorted arrays, sorting adds cost.

Lightning Quiz — 5 MCQs (Iterative)

1. Best-case time complexity of binary search?

O(1)
O(log n)
O(n)

2. Binary search requires the array to be:

sorted
unique elements only

3. Iterative binary search space complexity?

O(1)
O(log n)

4. If arr[mid] < target, next range is:

left..mid-1
mid+1..right

5. If target not present, function returns:

index
-1

Next Steps & Homework

• Convert Python code to JavaScript and run it in the browser console.
• Implement binary search to return the first occurrence if duplicates exist.
• Try searching for values not present and trace the steps.

Prepared by Champak Roy — Programmer's Picnic series.