Why Binary Search and What Sorted Order Gives You in DSA Python - Why It Works

Concept Flow - Why Binary Search and What Sorted Order Gives You

Start with sorted array

↓

Set low = 0, high = length-1

↓

Calculate mid = (low + high)//2

↓

Compare target with array[mid

↓

Set high=mid-1

↓

Repeat until low > high

↓

Target not found

Binary search works on sorted arrays by repeatedly dividing the search range in half, comparing the middle element to the target, and narrowing down the search until the target is found or the range is empty.

Execution Sample

DSA Python

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

This code searches for a target value in a sorted array using binary search and returns its index or -1 if not found.

Execution Table

Step	Operation	low	high	mid	arr[mid]	Comparison	Action	Search Range Visual
1	Initialize	0	6	-	-	-	Start search	[2, 4, 6, 8, 10, 12, 14]
2	Calculate mid	0	6	3	8	8 < 10?	arr[mid] < target, set low = mid + 1	[2, 4, 6, (8), 10, 12, 14]
3	Calculate mid	4	6	5	12	12 > 10?	arr[mid] > target, set high = mid - 1	[2, 4, 6, 8, 10, (12), 14]
4	Calculate mid	4	4	4	10	10 == 10?	Found target, return index 4	[2, 4, 6, 8, (10), 12, 14]
5	End	-	-	-	-	-	Search ends with target found at index 4	[2, 4, 6, 8, 10, 12, 14]

💡 Search ends when target is found or low > high (search range empty). Here, target found at index 4.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
low	0	4	4	4	4
high	6	6	4	4	4
mid	-	3	5	4	4
arr[mid]	-	8	12	10	10

Key Moments - 3 Insights

Why must the array be sorted for binary search to work?

Because binary search decides which half to search next by comparing the target with the middle element. If the array is not sorted, this logic fails. See execution_table rows 2 and 3 where decisions depend on arr[mid] compared to target.

Why do we update low to mid + 1 instead of mid when arr[mid] < target?

Because arr[mid] is already checked and not the target, so we exclude it from the next search range. This avoids infinite loops. See execution_table row 2 where low changes from 0 to 4.

What happens when low becomes greater than high?

It means the search range is empty and the target is not in the array. The loop ends and -1 is returned. This is the exit condition shown in the concept_flow and exit_note.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the value of 'high' after the operation?

A 4

B 6

C 5

D 3

💡 Hint

Check the 'high' column in execution_table row 3 after the action.

At which step does the search range reduce to a single element?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'low' and 'high' values in execution_table rows to find when low equals high.

If the array was not sorted, what would happen to the binary search process?

A It would still find the target correctly

B It might miss the target or give wrong results

C It would run faster

D It would return the first element always

💡 Hint

Refer to key_moments about why sorting is necessary for binary search.

Concept Snapshot

Binary Search requires a sorted array.
Start with low=0 and high=length-1.
Find mid = (low + high)//2.
Compare arr[mid] with target.
If equal, return mid.
If arr[mid]<target, search right half (low=mid+1).
If arr[mid]>target, search left half (high=mid-1).
Repeat until low > high (target not found).

Full Transcript

Binary search is a fast way to find a target value in a sorted array. It works by repeatedly dividing the search range in half. We start with low at 0 and high at the last index. We find the middle index mid and compare the middle element with the target. If they match, we return the index. If the middle element is less than the target, we move low to mid plus one to search the right half. If it is greater, we move high to mid minus one to search the left half. We repeat this until low is greater than high, which means the target is not in the array. This method only works if the array is sorted because the decision to go left or right depends on the order. The execution table shows each step with the current low, high, mid, and the element at mid, along with the action taken. The variable tracker shows how low, high, mid, and arr[mid] change at each step. Key moments clarify why sorting is needed, why we update low and high as we do, and what happens when the search ends. The visual quiz tests understanding of these steps and conditions.

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