Lower bound, upper bound, first/last occurrence.

Overview

Lower bound, upper bound, first/last occurrence.

Example 

  public static int binarySearch(int[] arr, int target) {
    int lo = 0, hi = arr.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

Common Use Cases

  • Finding elements in sorted collections
  • Search space reduction problems

Pitfalls to Avoid

  • Off-by-one errors in boundary conditions
  • Integer overflow in mid calculation
  • Collections.binarySearch
  • Two-pointer technique

Best Practices

  • Understand when to use binary search variations versus simpler alternatives
  • Write unit tests covering edge cases and failure paths
  • Follow Java conventions and prefer standard library APIs when available
  • Profile before optimizing — measure impact in your specific workload