Why Binary Search and What Sorted Order Gives You in DSA Go - 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 target with the middle element, and narrowing down the search until the target is found or the range is empty.

Execution Sample

DSA Go

func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    for low <= high {
        mid := (low + high) / 2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return -1
}

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

Execution Table

Step	Operation	low	high	mid	Compare arr[mid] with target	Action	Search Range	Result
1	Initialize	0	6	-	-	-	[2,4,6,8,10,12,14]	Continue
2	Calculate mid	0	6	3	arr[3]=8 vs target=10	8 < 10 → low=mid+1=4	[10,12,14]	Continue
3	Calculate mid	4	6	5	arr[5]=12 vs target=10	12 > 10 → high=mid-1=4	[10]	Continue
4	Calculate mid	4	4	4	arr[4]=10 vs target=10	Found target at index 4	[10]	Stop
5	Exit	-	-	-	-	-	-	Target found at index 4

💡 Search stops when target is found at index 4 or when low > high (not in this case).

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
target	10	10	10	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 steps 2 and 3 where the search range is narrowed based on comparisons.

Why do we update 'low' to mid+1 or 'high' to mid-1 instead of mid?

Because mid has already been checked and is not the target, so we exclude it from the next search range to avoid infinite loops. This is shown in execution_table steps 2 and 3 where low or high moves past mid.

What happens if the target is not in the array?

The search range eventually becomes empty (low > high), and the function returns -1. This is the exit condition after repeating the steps without finding the target.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of 'mid' at step 3?

A 3

B 5

C 4

D 6

💡 Hint

Check the 'mid' column in execution_table row for step 3.

At which step does the search range narrow to just one element?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Search Range' column in execution_table to see when it reduces to one element.

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

A It might miss the target because the search range decisions would be wrong.

B It would still find the target correctly.

C It would run faster.

D It would return the first element always.

💡 Hint

Refer to key_moments about why sorting is necessary.

Concept Snapshot

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

Full Transcript

Binary search is a fast way to find a number in a sorted list. We start by looking at the middle number. If it matches the target, we are done. If the target is bigger, we look only in the right half. If smaller, we look only in the left half. We keep cutting the search area in half until we find the target or run out of numbers. This only works if the list is sorted because we rely on order to decide which half to search next.