Sorting and searching become more powerful when students see them as planning tools. Sorting does not just arrange data. It can make duplicates adjacent, enable binary search, and support two-pointer strategies.
Binary search with a clear invariant
The invariant is the promise that if the target exists, it must be between low and high.
public static int binarySearch(int[] a, int target)
{
int low = 0;
int high = a.length - 1;
while (low <= high)
{
int mid = (low + high) / 2;
if (a[mid] == target)
return mid;
else if (a[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return -1;
}The update must exclude mid because that value has already been checked. Using low = mid or high = mid can cause an infinite loop.
Two-pointer example after sorting
Suppose we need to know whether any two scores sum to a target.
public static boolean hasPairSum(int[] a, int target)
{
Arrays.sort(a);
int left = 0;
int right = a.length - 1;
while (left < right)
{
int sum = a[left] + a[right];
if (sum == target)
return true;
else if (sum < target)
left++;
else
right--;
}
return false;
}Sorting makes the pointer logic possible. If the sum is too small, move the left pointer to a larger value. If the sum is too large, move the right pointer to a smaller value.
Stable sorting matters with records
If two students have the same score, a stable sort preserves their original order. That can matter when the original order represents signup time. If tie behavior matters, students should say it explicitly in the design.
Common traps
- Using binary search on unsorted data.
- Sorting by the wrong field in object records.
- Forgetting that sorting mutates arrays and many lists.
- Using nested loops for pair search when sorted two-pointer logic would work.
Practice prompt
Given anonymous app usage totals, find whether two students together reached exactly 120 minutes. Solve it once with nested loops and once with sorting plus two pointers. Compare the runtime and explain the tradeoff.