Why Binary Search and What Sorted Order Gives You in DSA Java - Performance Analysis

Time Complexity: Why Binary Search and What Sorted Order Gives You

O(log n)

Understanding Time Complexity

We want to understand why binary search is faster than simple searching methods.

How does having a sorted list help us find items quickly?

Scenario Under Consideration

Analyze the time complexity of the following binary search code.

public 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;
}
    

This code searches for a target number in a sorted array by repeatedly dividing the search range in half.

Identify Repeating Operations

Look at what repeats in the code.

• Primary operation: Checking the middle element and adjusting the search range.
• How many times: The search range halves each time until the target is found or range is empty.

How Execution Grows With Input

Each step cuts the search area in half, so the number of steps grows slowly as the list gets bigger.

Input Size (n)	Approx. Operations
10	About 4 checks
100	About 7 checks
1000	About 10 checks

Pattern observation: Doubling the input size adds only one extra step.

Final Time Complexity

Time Complexity: O(log n)

This means the number of steps grows very slowly even if the list gets much bigger.

Common Mistake

[X] Wrong: "Binary search works on any list, sorted or not."

[OK] Correct: Without sorting, you can't decide which half to ignore, so binary search won't work correctly.

Interview Connect

Knowing why binary search is fast and needs sorted data shows you understand how to choose the right tool for searching tasks.

Self-Check

"What if the array was not sorted but nearly sorted? How would that affect binary search's time complexity?"

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