Why Binary Search and What Sorted Order Gives You in DSA Java - Challenge Your Understanding

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Binary Search on Sorted Array

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

DSA Java

import java.util.Arrays;

public class BinarySearchDemo {
    public static void main(String[] args) {
        Integer[] arr = {2, 4, 6, 8, 10, 12};
        int index = Arrays.binarySearch(arr, 8);
        System.out.println(index);
    }
}

A -1

B 3

C 4

D 0

💡 Hint

Remember that binarySearch returns the index of the element if found.

The array is sorted in ascending order. The element 8 is at index 3 (0-based). So, binarySearch returns 3.

🧠 Conceptual

intermediate

Why Must the Array Be Sorted for Binary Search?

Why is it necessary for the array to be sorted before applying binary search?

A Because binary search requires the array to be in reverse order.

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

C Because binary search divides the array and compares the middle element to decide which half to search next.

D Because binary search can only find the first element in the array.

💡 Hint

Think about how binary search decides which half to continue searching.

Binary search compares the target with the middle element and decides to search left or right half. This logic only works if the array is sorted.

❓ Predict Output

advanced

Binary Search Result on Unsorted Array

What will be the output of this Java code that performs binary search on an unsorted array?

DSA Java

import java.util.Arrays;

public class BinarySearchUnsorted {
    public static void main(String[] args) {
        int[] arr = {2, 4, 10, 6, 12, 8};
        int index = Arrays.binarySearch(arr, 8);
        System.out.println(index);
    }
}

A -3

B 4

C -1

D 2

💡 Hint

Binary search on unsorted arrays returns a negative value indicating insertion point.

Since the array is not sorted, binarySearch returns a negative value indicating the insertion point where 8 would be placed to keep order. The value -3 means insertion at index 2.

🔧 Debug

advanced

Find the Bug in Binary Search Usage

Identify the problem in this Java code snippet that uses binary search on a sorted array.

DSA Java

import java.util.Arrays;

public class BuggyBinarySearch {
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9};
        int target = 4;
        int index = Arrays.binarySearch(arr, target);
        if (index >= 0) {
            System.out.println("Found at index " + index);
        } else {
            System.out.println("Not found");
        }
    }
}

A The array is not sorted, so binary search will fail.

B The binarySearch method requires a List, not an array.

C The target value 4 is not in the array, so it will cause an exception.

D The condition should be index >= 0 instead of index > 0.

💡 Hint

Check how binarySearch indicates found elements with index 0.

binarySearch returns 0 if the target is at index 0. The condition index > 0 misses this case, so it should be index >= 0.

🚀 Application

expert

Using Binary Search to Find First Occurrence in Sorted Array with Duplicates

Given a sorted array with duplicates, which approach correctly finds the first occurrence index of a target using binary search?

A Modify binary search to continue searching left half when target is found, updating result until leftmost index is found.

B Use standard binary search and return the first index found without further checks.

C Sort the array again before binary search to ensure duplicates are grouped.

D Use linear search instead because binary search cannot handle duplicates.

💡 Hint

Think about how to find the leftmost target index, not just any occurrence.

To find the first occurrence, binary search must continue searching the left half after finding the target, updating the result to the smallest index found.

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