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

Mental Model

Binary search quickly finds a value 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 open it in the middle, check if the word is before or after, then open the correct half again and again until you find it.

Sorted array: [1] -> [3] -> [5] -> [7] -> [9] -> [11] -> [13] -> null
Indices:      0      1      2      3      4       5       6
Search range: ↑-----------------------------↑

Dry Run Walkthrough

Input: array: [1, 3, 5, 7, 9, 11, 13], search for 9

Goal: Find the position of 9 quickly using binary search

Step 1: Check middle element at index 3 (value 7)

[1] -> [3] -> [5] -> [7↑] -> [9] -> [11] -> [13] -> null

Why: We start in the middle to decide which half to search next

Step 2: Since 9 > 7, move search to right half (indices 4 to 6)

[9] -> [11] -> [13] -> null (search range now indices 4 to 6)

Why: Because 9 is bigger than 7, it must be in the right half

Step 3: Check middle element at index 5 (value 11)

[9] -> [11↑] -> [13] -> null

Why: Check middle of new search range to narrow down further

Step 4: Since 9 < 11, move search to left half (index 4)

[9↑] -> null

Why: Because 9 is smaller than 11, it must be in the left half

Step 5: Check element at index 4 (value 9), found target

[9↑] -> null

Why: We found the value we were searching for

Result:

[9↑] -> null (value 9 found at index 4)

Annotated Code

DSA Java

public class BinarySearchDemo {
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // find middle index
            if (arr[mid] == target) {
                return mid; // found target
            } else if (arr[mid] < target) {
                left = mid + 1; // search right half
            } else {
                right = mid - 1; // search left half
            }
        }
        return -1; // target not found
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        int target = 9;
        int index = binarySearch(arr, target);
        if (index != -1) {
            System.out.println("Found " + target + " at index " + index);
        } else {
            System.out.println(target + " not found in array");
        }
    }
}

int mid = left + (right - left) / 2; // find middle index

Calculate middle index to split search range

if (arr[mid] == target) { return mid; }

Check if middle element is the target

else if (arr[mid] < target) { left = mid + 1; }

If target is bigger, move left pointer to right half

else { right = mid - 1; }

If target is smaller, move right pointer to left half

Output

Found 9 at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space

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

vs Alternative: Compared to linear search O(n), binary search is much faster on sorted data because it skips half the elements each time

Edge Cases

empty array

returns -1 immediately because left > right

DSA Java

while (left <= right) {

target smaller than all elements

search narrows until left > right, returns -1

DSA Java

while (left <= right) {

target larger than all elements

search narrows until left > right, returns -1

DSA Java

while (left <= right) {

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 step.

Common Mistakes

Mistake: Not checking if the array is sorted before using binary search
Fix: Always ensure the input array is sorted before applying binary search

Mistake: Calculating middle index as (left + right) / 2 which can cause overflow
Fix: Calculate middle as left + (right - left) / 2 to avoid overflow

Summary

Binary search finds a target value quickly by repeatedly dividing the search range in half.

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

The key insight is that sorted order lets you eliminate half the remaining items each step.

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