Binary Search as Divide and Conquer in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Binary Search Call

What is the output of the following Java code that performs a recursive binary search on the array?

DSA Java

public class BinarySearch {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) return -1;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target);
        else return binarySearch(arr, mid + 1, right, target);
    }
    public static void main(String[] args) {
        int[] data = {2, 4, 6, 8, 10, 12, 14};
        System.out.println(binarySearch(data, 0, data.length - 1, 10));
    }
}

A 4

B 3

C -1

D 5

💡 Hint

Remember array indices start at 0. Find the index where 10 is located.

The array is sorted. The element 10 is at index 4 (0-based). The binary search returns this index.

🧠 Conceptual

intermediate

Divide and Conquer Principle in Binary Search

Which statement best describes how binary search uses the divide and conquer approach?

A It divides the array into multiple parts and searches all parts simultaneously.

B It searches the entire array linearly after dividing it into halves.

C It combines all elements before searching to reduce the search space.

D It divides the array into two halves and recursively searches only the half that may contain the target.

💡 Hint

Think about how binary search reduces the problem size each step.

Binary search splits the array into two halves and only continues searching the half where the target could be, ignoring the other half.

❓ Predict Output

advanced

Output of Iterative Binary Search with Missing Element

What is the output of this iterative binary search code when searching for 7 in the array?

DSA Java

public class BinarySearchIterative {
    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;
            if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] data = {1, 3, 5, 9, 11};
        System.out.println(binarySearch(data, 7));
    }
}

A -1

B 0

C 3

D 2

💡 Hint

7 is not in the array. What does the code return when the element is missing?

Since 7 is not present, the search ends with left > right and returns -1 indicating not found.

🔧 Debug

advanced

Identify the Error in Recursive Binary Search

What error will this recursive binary search code produce when searching for 5 in the array?

DSA Java

public class BinarySearchBug {
    public static int binarySearch(int[] arr, int left, int right, int target) {
        if (left > right) return -1;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] > target) return binarySearch(arr, left, mid - 1, target);
        else return binarySearch(arr, mid + 1, right, target);
    }
    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 5};
        System.out.println(binarySearch(data, 0, data.length - 1, 5));
    }
}

A Returns correct index 4

B StackOverflowError due to infinite recursion

C Returns -1 even though 5 is in the array

D Compilation error due to missing return statement

💡 Hint

Check the base case condition carefully.

The base case uses 'left >= right' which excludes the case when left == right, missing the last element check. So it returns -1 incorrectly.

🧠 Conceptual

expert

Time Complexity of Binary Search Divide and Conquer

What is the time complexity of binary search and why does the divide and conquer approach achieve this?

A O(n log n) because it divides and sorts the array before searching

B O(log n) because the problem size halves each step, reducing search space exponentially

C O(1) because it finds the element immediately using divide and conquer

D O(n) because it checks each element after dividing the array

💡 Hint

Think about how many times you can halve the array before it becomes size 1.

Binary search halves the search space each step, so the number of steps grows logarithmically with input size.

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