Sorting and Searching

Sorting and Searching

Now that we've covered Arrays and Strings, Linked Lists, Stacks and Queues, and the basics of Trees and Graphs, you're ready for one of the most common interview themes: organize data, then find what you need fast.

Sorting and searching show up everywhere in MAANG-style problems:

• Find a missing number
• Detect duplicates
• Match pairs or intervals
• Find the first/last occurrence
• Optimize a brute-force scan

The key idea: sorting often turns a messy problem into a structured one. Once data is ordered, searching can become dramatically faster.

The Sorted Data Superpower

An unsorted array gives you very little information:

[9, 2, 7, 4, 1]

If you're looking for 4, you may need to check every element.

But a sorted array gives you structure:

[1, 2, 4, 7, 9]

Now each comparison tells you which side to ignore. If you check the middle and your target is smaller, everything to the right can be discarded.

Interview mindset

When you see an array problem, ask:

1. Is the input already sorted?
2. Am I allowed to sort it?
3. Would sorting destroy information I need, like original indices?
4. Will sorting reduce a nested loop into a smarter scan or search?

Sorting in Java

In interviews, you usually don't need to implement a full sorting algorithm unless asked. Java gives you reliable tools:

• Arrays.sort(array) for arrays
• Collections.sort(list) or list.sort(...) for lists
• Arrays.binarySearch(array, target) for searching a sorted array

Important: binary search only works correctly after the data is sorted.

Here's a small Java example using built-in sorting and searching.

```java
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] nums = {9, 2, 7, 4, 1};

        System.out.println("Before sort: " + Arrays.toString(nums));

        Arrays.sort(nums);
        System.out.println("After sort:  " + Arrays.toString(nums));

        int target = 4;
        int index = Arrays.binarySearch(nums, target);

        System.out.println("Target " + target + " found at index: " + index);
    }
}
```

Sorting Algorithm Tradeoffs

You don't need to memorize every sorting algorithm on day one, but you should recognize the main performance tiers.

Simple sorts

Examples: bubble sort, selection sort, insertion sort

• Usually O(n^2) time
• Easy to understand
• Often too slow for large interview inputs

Efficient comparison sorts

Examples: merge sort, quicksort, heap sort

• Usually around O(n log n) time
• Used in real libraries and serious interview solutions

Java note

Java's built-in sorting is optimized:

• Primitive arrays like int[] use highly tuned sorting internally
• Object arrays and lists use stable sorting behavior

In interviews, your bigger job is often deciding whether sorting helps the problem, not rewriting Java's sort from scratch.

Linear Search vs Binary Search

From Arrays and Strings, you already know single-pass scanning. That is linear search:

• Check items one by one
• Works on unsorted data
• Time: O(n)

Binary search is different:

• Requires sorted data
• Checks the middle
• Discards half the search space each step
• Time: O(log n)

Let's compare both in Java.

```java
public class Main {
    public static int linearSearch(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == target) {
                return i;
            }
        }
        return -1;
    }

    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] unsorted = {9, 2, 7, 4, 1};
        int[] sorted = {1, 2, 4, 7, 9};

        System.out.println("Linear search index: " + linearSearch(unsorted, 4));
        System.out.println("Binary search index: " + binarySearch(sorted, 4));
    }
}
```

You want to use binary search on an array. Which condition is required for the standard binary search algorithm to work correctly?

True or false: If you need to search for one target one time in an unsorted array, sorting first always improves the total time complexity.

Binary search on n sorted elements runs in ____ time.

Common Binary Search Mistakes

Binary search is short, but easy to get subtly wrong.

Watch for:

• Using binary search on unsorted data
• Infinite loops from incorrect boundary updates
• Off-by-one errors with left, right, and mid
• Overflow risk from (left + right) / 2

Prefer this safer midpoint formula:

mid = left + (right - left) / 2

A useful interview variation is finding the first position where a value could be inserted while keeping the array sorted. This is often called lower bound.

```java
import java.util.Arrays;

public class Main {
    public static int lowerBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length; // notice: right is one past the last index

        while (left < right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 4, 4, 4, 7, 9};
        int target = 4;

        System.out.println("Array: " + Arrays.toString(nums));
        System.out.println("First position for " + target + ": " + lowerBound(nums, target));
        System.out.println("Insert position for 6: " + lowerBound(nums, 6));
    }
}
```

How to Use This in Interviews

When a problem involves finding, matching, or ranking values, run this quick checklist:

1. Can I solve it with a direct scan?
   Start simple. A correct O(n) idea is better than a broken clever one.

2. Would sorting reveal structure?
   Sorting can help with pairs, duplicates, intervals, and closest values.

3. Am I allowed to reorder the input?
   If original positions matter, store pairs like (value, originalIndex) or choose a different approach.

4. Can binary search replace repeated scanning?
   If data is sorted, searching can drop from O(n) to O(log n).

5. What is the total cost?
   Sorting plus searching is often O(n log n + log n), which simplifies to O(n log n).

Next, we'll move into Recursion and Backtracking, where you'll learn how to explore decision paths systematically.