Why Binary Search and What Sorted Order Gives You in DSA Java - 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

↓

Found

↓

high = mid - 1

↓

Repeat until low > high

↓

Not Found

Binary search works on a sorted array 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 Java

int binarySearch(int[] arr, int target) {
  int low = 0, high = arr.length - 1;
  while (low <= high) {
    int mid = low + (high - low) / 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	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?	No	[2, 4, 6, (8), 10, 12, 14]
3	Compare target > arr[mid]	0	6	3	8	10 > 8?	Yes, low = mid+1=4	[10, 12, 14]
4	Calculate mid	4	6	5	12	12 == 10?	No	[10, (12), 14]
5	Compare target < arr[mid]	4	6	5	12	10 < 12?	Yes, high = mid-1=4	[10]
6	Calculate mid	4	4	4	10	10 == 10?	Yes, found at index 4	[ (10) ]
7	End	4	4	4	10	-	Return index 4	[ (10) ]

💡 Search ends 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	After Step 5	After Step 6	Final
low	0	0	4	4	4	4	4
high	6	6	6	6	4	4	4
mid	-	3	3	5	5	4	4
arr[mid]	-	8	8	12	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 decision is invalid. See execution_table steps 3 and 5 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 3 and 5 where low and high move past mid.

What happens if the target is not in the array?

The search range shrinks until low becomes greater than high, meaning no elements left to check. The loop ends and returns -1. This is the exit condition described in the concept_flow and exit_note.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the value of mid and arr[mid]?

A mid = 4, arr[mid] = 10

B mid = 5, arr[mid] = 12

C mid = 3, arr[mid] = 8

D mid = 6, arr[mid] = 14

💡 Hint

Check the 'mid' and 'arr[mid]' columns in execution_table row with Step 4.

At which step does the search find the target value?

A Step 3

B Step 5

C Step 6

D Step 7

💡 Hint

Look for the step where 'Comparison' shows equality and 'Action' says 'found'.

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

A It might miss the target because the search halves are invalid.

B It would run faster.

C It would still find the target correctly.

D It would return the first element always.

💡 Hint

Refer to key_moments about why sorting is required 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 target with arr[mid].
If equal, return mid.
If target < arr[mid], search left half.
Else, search right half.
Repeat until low > high (not 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 smaller, we look only in the left half. If larger, we look in the right 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. The code example shows how low, high, and mid change each step. When the target is found, the search stops and returns the index. If not found, it returns -1. This method is much faster than checking every number one by one.

Practice

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

easy

A. Because binary search divides the array and compares middle elements, which requires sorted order to decide direction

B. Because binary search works on any array regardless of order

C. Because binary search only works on arrays with unique elements

D. Because binary search requires the array to be reversed

Solution

1. Step 1: Understand binary search mechanism

   Binary search picks the middle element and compares it to the target to decide whether to search left or right.

2. Step 2: Importance of sorted order

   Without sorted order, we cannot decide which half to discard because elements are unordered.

3. Final Answer:

   Because binary search divides the array and compares middle elements, which requires sorted order to decide direction -> Option A

4. Quick Check:

   Sorted array needed for binary search direction [OK]

Hint: Binary search needs sorted data to decide left or right half [OK]

Common Mistakes:

• Thinking binary search works on unsorted arrays
• Believing binary search requires unique elements
• Confusing binary search with linear search

2. Which of the following is the correct syntax to perform binary search on a sorted array arr in Java using Arrays.binarySearch()?

easy

A. int index = Arrays.binarySearch(arr, target);

B. int index = Arrays.searchBinary(arr, target);

C. int index = binarySearch(arr, target);

D. int index = arr.binarySearch(target);

Solution

1. Step 1: Recall Java binary search method

   Java's standard library provides Arrays.binarySearch(array, key) to search sorted arrays.

2. Step 2: Check method call syntax

   The method is static in Arrays class, so call is Arrays.binarySearch(arr, target).

3. Final Answer:

   int index = Arrays.binarySearch(arr, target); -> Option A

4. Quick Check:

   Correct Java binary search syntax = int index = Arrays.binarySearch(arr, target); [OK]

Hint: Use Arrays.binarySearch(arr, target) for Java binary search [OK]

Common Mistakes:

• Using wrong method name like searchBinary
• Calling binarySearch on array instance
• Missing static class Arrays

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

int[] arr = {2, 4, 6, 8, 10};
int index = Arrays.binarySearch(arr, 6);
System.out.println(index);

medium

A. 3

B. -1

C. 0

D. 2

Solution

1. Step 1: Understand array and target

   Array is sorted: {2,4,6,8,10}. Target is 6.

2. Step 2: Find index of 6 in array

   6 is at index 2 (0-based indexing).

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Index of 6 in arr = 2 [OK]

Hint: Index returned is position of target in sorted array [OK]

Common Mistakes:

• Confusing index with value
• Assuming binarySearch returns -1 if found
• Using 1-based indexing

4. Identify the error in the following code snippet that tries to use binary search on an unsorted array:

int[] arr = {5, 2, 9, 1, 7};
int index = Arrays.binarySearch(arr, 7);
System.out.println(index);

medium

A. binarySearch method does not exist in Arrays class

B. The array must be sorted before calling binarySearch

C. The target value 7 is not present in the array

D. The array should be declared as List, not int[]

Solution

1. Step 1: Check array order

   The array {5,2,9,1,7} is unsorted.

2. Step 2: Understand binarySearch requirement

   Binary search requires sorted arrays to work correctly.

3. Final Answer:

   The array must be sorted before calling binarySearch -> Option B

4. Quick Check:

   Binary search needs sorted array [OK]

Hint: Always sort array before binary search [OK]

Common Mistakes:

• Ignoring array sorting requirement
• Assuming binarySearch works on any array
• Thinking target absence causes error

5. Given a sorted array arr = {1, 3, 5, 7, 9, 11}, you want to find the index of the number 8 using binary search. What will be the result and why?

hard

A. -1 because 8 is not in the array

B. 6 because 8 would be inserted at the end

C. -5 because binarySearch returns negative insertion point minus 1

D. 3 because 8 is closest to 7 at index 3

Solution

1. Step 1: Check if 8 is in the array

   Array is {1,3,5,7,9,11}, 8 is not present.

2. Step 2: Understand binarySearch return for missing elements

   Java's binarySearch returns -(insertion_point) - 1 if element not found. 8 would be inserted at index 4 (between 7 and 9), so return is -(4) - 1 = -5.

3. Final Answer:

   -5 because binarySearch returns negative insertion point minus 1 -> Option C

4. Quick Check:

   Missing element returns negative insertion point minus 1 [OK]

Hint: Missing element returns -(insertion_point) - 1 [OK]

Common Mistakes:

• Assuming -1 means not found always
• Returning closest index instead of negative value
• Confusing insertion point calculation