Binary Search as Divide and Conquer in DSA Java

Mental Model

Binary search splits a sorted list into halves to quickly find a target value by ignoring half the list each time.

Analogy: Imagine looking for a word in a dictionary by opening it in the middle, then deciding if the word is in the first or second half, and repeating this until you find it.

Sorted array: [1, 3, 5, 7, 9, 11, 13]
Indices:      [0, 1, 2, 3, 4,  5,  6]
Pointers:     low=0 ↑          mid=3 ↑          high=6 ↑

Dry Run Walkthrough

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

Goal: Find the index of target 9 using binary search

Step 1: Calculate mid index between low=0 and high=6; mid=3; compare array[mid]=7 with target=9

[1, 3, 5, 7, 9, 11, 13]
 low=0 ↑ mid=3 ↑ high=6 ↑

Why: We check middle element to decide which half to search next

Step 2: Since 7 < 9, move low to mid+1=4 to search right half

[1, 3, 5, 7, 9, 11, 13]
       low=4 ↑ mid=? high=6 ↑

Why: Target must be in the right half because 7 is less than 9

Step 3: Calculate mid between low=4 and high=6; mid=5; compare array[mid]=11 with target=9

[1, 3, 5, 7, 9, 11, 13]
       low=4 ↑ mid=5 ↑ high=6 ↑

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

Step 4: Since 11 > 9, move high to mid-1=4 to search left half

[1, 3, 5, 7, 9, 11, 13]
       low=4 ↑ mid=? high=4 ↑

Why: Target must be in left half because 11 is greater than 9

Step 5: Calculate mid between low=4 and high=4; mid=4; compare array[mid]=9 with target=9

[1, 3, 5, 7, 9, 11, 13]
       low=4 ↑ mid=4 ↑ high=4 ↑

Why: Check the only element left in the search range

Step 6: Found target at index 4; return index 4

[1, 3, 5, 7, 9, 11, 13]
       low=4 ↑ mid=4 ↑ high=4 ↑

Why: Target matches the middle element, search ends

Result:

Final state: [1, 3, 5, 7, 9, 11, 13]
Target 9 found at index 4

Annotated Code

DSA Java

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

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

int mid = low + (high - low) / 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) { low = mid + 1; }

If middle element less than target, search right half

else { high = mid - 1; }

If middle element greater than target, search left half

Output

Target 9 found at index 4

Complexity Analysis

Time: O(log n) because each step halves the search space until the target is found or range is empty

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 arrays by cutting search space in half each step

Edge Cases

Empty array

Returns -1 immediately because low > high

DSA Java

while (low <= high) {

Target not in array

Search narrows until low > high, then returns -1

DSA Java

while (low <= high) {

Single element array with target present

Checks single element and returns index if matches

DSA Java

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

When to Use This Pattern

When you need to find an item quickly in a sorted list, look for binary search because it divides the problem in half each step to speed up search.

Common Mistakes

Mistake: Calculating mid as (low + high) / 2 can cause integer overflow
Fix: Calculate mid as low + (high - low) / 2 to avoid overflow

Mistake: Not updating low or high correctly causing infinite loop
Fix: Ensure low = mid + 1 and high = mid - 1 updates are correct based on comparison

Summary

Binary search finds a target in a sorted array by repeatedly dividing the search range in half.

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

The key insight is to compare the middle element and discard half the list each time.

Practice

1. What is the main idea behind Binary Search as a divide and conquer algorithm?

easy

A. It searches every element one by one from start to end.

B. It divides the search space into two halves and eliminates one half each time.

C. It sorts the array before searching.

D. It uses recursion to add elements.

Solution

1. Step 1: Understand divide and conquer in binary search

   Binary search splits the sorted array into two halves and decides which half to continue searching in.

2. Step 2: Eliminate half the search space

   By comparing the middle element with the target, it discards one half, reducing the problem size quickly.

3. Final Answer:

   It divides the search space into two halves and eliminates one half each time. -> Option B

4. Quick Check:

   Divide and conquer = split and discard half [OK]

Hint: Binary search halves the search space each step [OK]

Common Mistakes:

• Thinking binary search checks every element
• Confusing binary search with sorting
• Believing binary search adds elements

2. Which of the following is the correct Java method signature for a binary search function on an integer array?

easy

A. public static int binarySearch(int[] arr, int target)

B. int binarySearch(int arr[], target)

C. public int binarySearch(int[] arr, int target, int start, int end)

D. static void binarySearch(int[] arr, int target)

Solution

1. Step 1: Check method signature correctness

   public static int binarySearch(int[] arr, int target) uses public static, returns int index, and has correct parameter types and order.

2. Step 2: Compare other options

   int binarySearch(int arr[], target) misses access modifier and parameter type for target; public int binarySearch(int[] arr, int target, int start, int end) has extra parameters but no static; static void binarySearch(int[] arr, int target) returns void which is incorrect for search.

3. Final Answer:

   public static int binarySearch(int[] arr, int target) -> Option A

4. Quick Check:

   Correct signature returns int and uses static [OK]

Hint: Binary search returns index as int, not void [OK]

Common Mistakes:

• Omitting static keyword
• Wrong return type (void instead of int)
• Missing parameter types

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

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

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

medium

A. 2

B. 3

C. -1

D. 0

Solution

1. Step 1: Identify the target and array

   The array is [2,4,6,8,10], target is 6.

2. Step 2: Trace binary search steps

   Initial left=0, right=4, mid=2; arr[2]=6 equals target, so return 2.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Index of 6 in array = 2 [OK]

Hint: Check middle element index for target match first [OK]

Common Mistakes:

• Confusing index with value
• Off-by-one errors in mid calculation
• Returning wrong index when target found

4. Find the error in the following binary search code and choose the correct fix.

public static int binarySearch(int[] arr, int target) {
    int left = 0, right = arr.length;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

medium

A. Change mid calculation to mid = left - right to fix mid index.

B. Change while condition to left < right to fix infinite loop.

C. Change right to arr.length - 1 to avoid ArrayIndexOutOfBoundsException.

D. Remove else if and use only if statements.

Solution

1. Step 1: Identify array bounds usage

   Right is set to arr.length, which is out of array index range (max index is length-1).

2. Step 2: Fix right boundary

   Set right = arr.length - 1 to prevent accessing invalid index and avoid runtime error.

3. Final Answer:

   Change right to arr.length - 1 to avoid ArrayIndexOutOfBoundsException. -> Option C

4. Quick Check:

   Array indices go from 0 to length-1 [OK]

Hint: Array last index is length minus one [OK]

Common Mistakes:

• Setting right to arr.length causes index error
• Incorrect mid calculation
• Changing loop condition incorrectly

5. You have a sorted array with duplicate elements: int[] arr = {1, 2, 2, 2, 3, 4}. How would you modify binary search to find the first occurrence of the target 2?

hard

A. Modify mid calculation to always pick left middle element.

B. Return the first found index immediately without further checks.

C. Use linear search instead of binary search for duplicates.

D. After finding target, continue searching left half to find earlier occurrence.

Solution

1. Step 1: Understand duplicate handling in binary search

   Standard binary search returns any matching index, not necessarily first occurrence.

2. Step 2: Modify search to find first occurrence

   When target found, move right pointer to mid-1 to continue searching left side for earlier matches.

3. Final Answer:

   After finding target, continue searching left half to find earlier occurrence. -> Option D

4. Quick Check:

   Find first occurrence by searching left after match [OK]

Hint: On match, search left half to find first duplicate [OK]

Common Mistakes:

• Stopping at first found index
• Using linear search unnecessarily
• Changing mid calculation without reason