Why Binary Search and What Sorted Order Gives You in DSA Java - See It Work

Why Binary Search and What Sorted Order Gives You

📖 Scenario: Imagine you have a phone book with names sorted alphabetically. You want to find a friend's phone number quickly without checking every name one by one.

🎯 Goal: You will create a sorted list of names and use binary search to find if a specific name is in the list. This shows why sorting helps you search faster.

📋 What You'll Learn

Create a sorted array of names

Create a variable for the name to search

Use binary search logic to find the name

Print the result showing if the name was found or not

💡 Why This Matters

🌍 Real World

Searching sorted data quickly is useful in phone books, dictionaries, and databases.

💼 Career

Understanding binary search and sorting is fundamental for software development and technical interviews.

1

Create a sorted array of names

Create a String array called names with these exact values in this order: "Alice", "Bob", "Charlie", "Diana", "Eve"

DSA Java

// Create the sorted array of names
// Your code here

Hint

Use curly braces to list the names in order inside the array.

2

Create a variable for the name to search

Create a String variable called target and set it to "Charlie"

DSA Java

public class Main {
    public static void main(String[] args) {
        String[] names = {"Alice", "Bob", "Charlie", "Diana", "Eve"};
        // Create the target name to search
        // Your code here
    }
}

Hint

Use String target = "Charlie"; to create the variable.

3

Use binary search logic to find the name

Write a while loop using variables left, right, and mid to perform binary search on names to find target. Set a boolean variable found to true if target is found, otherwise false

DSA Java

public class Main {
    public static void main(String[] args) {
        String[] names = {"Alice", "Bob", "Charlie", "Diana", "Eve"};
        String target = "Charlie";
        
        // Implement binary search to find target
        // Your code here
    }
}

Hint

Use compareTo to compare strings and adjust left and right accordingly.

4

Print the result showing if the name was found or not

Write a System.out.println statement that prints "Found" if found is true, otherwise prints "Not Found"

DSA Java

public class Main {
    public static void main(String[] args) {
        String[] names = {"Alice", "Bob", "Charlie", "Diana", "Eve"};
        String target = "Charlie";
        
        int left = 0;
        int right = names.length - 1;
        boolean found = false;
        
        while (left <= right) {
            int mid = (left + right) / 2;
            int cmp = target.compareTo(names[mid]);
            if (cmp == 0) {
                found = true;
                break;
            } else if (cmp < 0) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        // Print if target was found or not
        // Your code here
    }
}

Hint

Use an if statement to check found and print the correct message.

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