Why Binary Search and What Sorted Order Gives You in DSA Python - Why This Pattern

Mental Model

Binary search quickly finds a number by repeatedly cutting the search area in half, but it only works if the list is sorted.

Analogy: Imagine looking for a word in a dictionary. You don't check every page; you open near the middle, see if your word is before or after, then open halfway in that half, and so on.

Sorted list: 1 -> 3 -> 5 -> 7 -> 9 -> 11 -> 13 -> 15 -> null
Search range: [start ↑] -> ... -> [mid ↑] -> ... -> [end ↑]

Dry Run Walkthrough

Input: list: 1->3->5->7->9->11->13->15, search for 9

Goal: Find the number 9 efficiently using binary search on a sorted list

Step 1: Set start at index 0, end at index 7 (full list range)

start=0, end=7, list=[1,3,5,7,9,11,13,15]

Why: We begin searching the entire list

Step 2: Calculate mid = (0+7)//2 = 3, check value at mid (7)

mid=3 -> value=7

Why: Check middle element to decide which half to search next

Step 3: Since 9 > 7, move start to mid+1 = 4

start=4, end=7

Why: 9 must be in the right half because list is sorted

Step 4: Calculate mid = (4+7)//2 = 5, check value at mid (11)

mid=5 -> value=11

Why: Check middle element of new range

Step 5: Since 9 < 11, move end to mid-1 = 4

start=4, end=4

Why: 9 must be in the left half of current range

Step 6: Calculate mid = (4+4)//2 = 4, check value at mid (9)

mid=4 -> value=9

Why: Found the target value

Result:

Final state: start=4, end=4, mid=4 -> value=9
Answer: Found 9 at index 4

Annotated Code

DSA Python

class BinarySearch:
    def __init__(self, data):
        self.data = data

    def search(self, target):
        start, end = 0, len(self.data) - 1
        while start <= end:
            mid = (start + end) // 2
            if self.data[mid] == target:
                return mid
            elif self.data[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return -1

# Driver code
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15]
bs = BinarySearch(sorted_list)
index = bs.search(9)
if index != -1:
    print(f"Found 9 at index {index}")
else:
    print("9 not found")

start, end = 0, len(self.data) - 1

Initialize search range to entire list

while start <= end:

Continue searching while range is valid

mid = (start + end) // 2

Find middle index of current range

if self.data[mid] == target:

Check if middle element is the target

elif self.data[mid] < target:

If middle element less than target, search right half

start = mid + 1

Move start to right half

else:

If middle element greater than target, search left half

end = mid - 1

Move end to left half

Output

Found 9 at index 4

Complexity Analysis

Time: O(log n) because each step halves the search range, quickly narrowing down the target

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Compared to linear search's O(n), binary search is much faster on large sorted lists because it skips half the elements each step

Edge Cases

Empty list

Returns -1 immediately because start > end

DSA Python

while start <= end:

Target not in list

Search narrows until start > end, then returns -1

DSA Python

while start <= end:

Single element list with target present

Finds target at mid immediately

DSA Python

if self.data[mid] == target:

When to Use This Pattern

When you need to find an item quickly in a sorted list, reach for binary search because it cuts the search space in half each time.

Common Mistakes

Mistake: Trying binary search on an unsorted list
Fix: Always sort the list first or use a different search method

Mistake: Using start < end instead of start <= end in loop condition
Fix: Use start <= end to ensure the last element is checked

Mistake: Calculating mid as (start + end) which can overflow in some languages
Fix: Use mid = start + (end - start) // 2 to avoid overflow (not critical in Python)

Summary

Binary search finds a target by repeatedly dividing a sorted list in half.

Use it when you have a sorted list and want fast search.

The key insight is that sorted order lets you skip half the list each step.

Practice

1. Why is binary search only applicable on a sorted list?

easy

A. Because it divides the search space based on order to find elements quickly

B. Because it can search any list regardless of order

C. Because it uses random guessing to find elements

D. Because it checks every element one by one

Solution

1. Step 1: Understand binary search method

   Binary search works by repeatedly dividing the list into halves and deciding which half to search next based on order.

2. Step 2: Importance of sorted order

   If the list is not sorted, we cannot decide which half to discard, so binary search fails.

3. Final Answer:

   Because it divides the search space based on order to find elements quickly -> Option A

4. Quick Check:

   Binary search needs sorted list = Because it divides the search space based on order to find elements quickly [OK]

Hint: Binary search needs order to skip halves fast [OK]

Common Mistakes:

• Thinking binary search works on unsorted lists
• Confusing binary search with linear search
• Believing binary search guesses randomly

2. Which of the following is the correct syntax to perform binary search using Python's bisect module on a sorted list arr to find position of x?

easy

A. pos = bisect.find(arr, x)

B. pos = bisect.search(arr, x)

C. pos = bisect.bisect_left(arr, x)

D. pos = bisect.index(arr, x)

Solution

1. Step 1: Recall bisect module functions

   The bisect module provides bisect_left to find insertion position for x in sorted arr.

2. Step 2: Check options for correct function

   Only bisect_left is valid; others like search, find, index do not exist in bisect.

3. Final Answer:

   pos = bisect.bisect_left(arr, x) -> Option C

4. Quick Check:

   bisect_left finds position = pos = bisect.bisect_left(arr, x) [OK]

Hint: Use bisect_left for binary search position in Python [OK]

Common Mistakes:

• Using non-existent bisect functions
• Confusing bisect with list methods
• Trying to use bisect on unsorted lists

3. What will be the output of the following code?

arr = [2, 4, 6, 8, 10]
left, right = 0, len(arr) - 1
x = 6
while left <= right:
    mid = (left + right) // 2
    if arr[mid] == x:
        print(mid)
        break
    elif arr[mid] < x:
        left = mid + 1
    else:
        right = mid - 1
else:
    print(-1)

medium

A. 2

B. 3

C. -1

D. 0

Solution

1. Step 1: Trace binary search steps

   Initial left=0, right=4, mid=2 (value 6). Since arr[mid] == x, print mid=2 and break.

2. Step 2: Confirm output

   The loop breaks after printing 2, so output is 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Index of 6 in arr is 2 [OK]

Hint: Check mid index value equals target to stop [OK]

Common Mistakes:

• Miscomputing mid index
• Confusing index with value
• Forgetting to break loop on find

4. The following code is intended to perform binary search on a sorted list nums to find target. What is the error?

def binary_search(nums, target):
    left, right = 0, len(nums)
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

medium

A. left should start from 1 instead of 0

B. right should be initialized as len(nums) - 1

C. mid calculation should be (left - right) // 2

D. The loop condition should be while left < right

Solution

1. Step 1: Check initialization of right pointer

   right is set to len(nums), which is out of index range since list indices go from 0 to len(nums)-1.

2. Step 2: Correct right initialization

   right should be len(nums) - 1 to avoid index error when accessing nums[mid].

3. Final Answer:

   right should be initialized as len(nums) - 1 -> Option B

4. Quick Check:

   Index max = len(nums)-1 [OK]

Hint: Right pointer max index is length minus one [OK]

Common Mistakes:

• Setting right to length causes index error
• Changing left start incorrectly
• Wrong mid calculation formula

5. You have a sorted list of unique integers representing book IDs: books = [101, 203, 305, 407, 509]. You want to find the position to insert a new book ID 400 so the list remains sorted. Which approach correctly finds the insertion index using binary search logic?

hard

A. Use linear search to find first element greater than 400 and insert before it

B. Insert 400 at the end always because list is sorted

C. Insert 400 at index 0 always to keep list sorted

D. Check middle element; if less than 400, move right pointer; else move left pointer until left > right, then insert at left

Solution

1. Step 1: Understand binary search insertion logic

   Binary search narrows down where to insert by comparing middle element with target and adjusting pointers.

2. Step 2: Apply logic to find insertion index

   When left pointer passes right, left is the correct insertion index to keep list sorted.

3. Final Answer:

   Check middle element; if less than 400, move right pointer; else move left pointer until left > right, then insert at left -> Option D

4. Quick Check:

   Binary search insertion index = Check middle element; if less than 400, move right pointer; else move left pointer until left > right, then insert at left [OK]

Hint: Insert at left pointer after binary search ends [OK]

Common Mistakes:

• Inserting at wrong fixed position
• Using linear search instead of binary
• Not updating pointers correctly