Given a sorted list and a target value, find the starting and ending position of the target. If not found, return [-1, -1]. Optimize for O(log n) time.

Overview

This problem extends binary search to find the first (leftmost) and last (rightmost) occurrences of a target value in a sorted array containing duplicates. It's a common variant that tests your ability to modify standard binary search for specific requirements.

Problem statement:

• Input: Sorted array
  textCopy

  [1, 2, 3, 3, 3, 4, 5]

  , target
  textCopy

  3

• Output:
  textCopy

  [2, 4]

  (indices of first and last occurrence)
• If not found:
  textCopy

  [-1, -1]

Key challenge: Achieve O(log n) time, not O(n)!

Real-world applications:

• Finding date ranges in logs
• Database range queries on indexed columns
• Finding price ranges in sorted product lists
• Version control (find first/last commit in range)

Algorithm Explanation

Standard binary search finds any occurrence of the target. For this problem, we need two modified binary searches:

1. Find First (Leftmost) Occurrence:

   • When we find the target, don't return immediately
   • Continue searching the left half to find earlier occurrences
   • Keep track of the rightmost left occurrence found

2. Find Last (Rightmost) Occurrence:

   • When we find the target, don't return immediately
   • Continue searching the right half to find later occurrences
   • Keep track of the leftmost right occurrence found

Visual Example:

textCopy
Array: [5, 7, 7, 8, 8, 8, 8, 10]
Target: 8

Find First (index 3):
  [5, 7, 7, |8|, 8, 8, 8, 10]  mid=3, found 8, search left
  [5, 7, 7]                     mid=1, 7<8, search right
  [7, 7]                        mid=2, 7<8, search right
  Empty                         return saved index 3

Find Last (index 6):
  [5, 7, 7, |8|, 8, 8, 8, 10]  mid=3, found 8, search right
  [8, 8, 8, 10]                mid=5, found 8, search right
  [8, 10]                      mid=6, found 8, search right
  [10]                         10>8, done, return 6

Approach 1: Two Separate Binary Searches (Optimal)

Run binary search twice - once for first, once for last.

dartCopy
List<int> findFirstAndLast(List<int> arr, int target) {
  int first = findFirst(arr, target);

  // If not found, return [-1, -1]
  if (first == -1) {
    return [-1, -1];
  }

  int last = findLast(arr, target);
  return [first, last];
}

int findFirst(List<int> arr, int target) {
  int left = 0;
  int right = arr.length - 1;
  int result = -1;

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

    if (arr[mid] == target) {
      result = mid;        // Save this occurrence
      right = mid - 1;     // Continue searching left
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

int findLast(List<int> arr, int target) {
  int left = 0;
  int right = arr.length - 1;
  int result = -1;

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

    if (arr[mid] == target) {
      result = mid;        // Save this occurrence
      left = mid + 1;      // Continue searching right
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

void main() {
  List<int> nums = [5, 7, 7, 8, 8, 8, 8, 10];

  print(findFirstAndLast(nums, 8));   // [3, 6]
  print(findFirstAndLast(nums, 7));   // [1, 2]
  print(findFirstAndLast(nums, 6));   // [-1, -1]
}

Time Complexity: O(log n) - two binary searches Space Complexity: O(1) - only pointer variables

Approach 2: Single Binary Search + Linear Expansion

Find any occurrence, then expand left/right. Not optimal but simpler.

dartCopy
List<int> findFirstAndLastLinear(List<int> arr, int target) {
  int index = binarySearch(arr, target);

  if (index == -1) {
    return [-1, -1];
  }

  // Expand left to find first
  int first = index;
  while (first > 0 && arr[first - 1] == target) {
    first--;
  }

  // Expand right to find last
  int last = index;
  while (last < arr.length - 1 && arr[last + 1] == target) {
    last++;
  }

  return [first, last];
}

int binarySearch(List<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;
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Time Complexity: O(log n + k) where k = number of duplicates Worst case: O(n) if all elements are the same!

When to use: Quick prototype, k is small

Approach 3: Unified Search Function

Reuse code with a direction parameter.

dartCopy
List<int> findFirstAndLastUnified(List<int> arr, int target) {
  int first = searchBound(arr, target, true);  // Find left bound

  if (first == -1) return [-1, -1];

  int last = searchBound(arr, target, false);  // Find right bound
  return [first, last];
}

int searchBound(List<int> arr, int target, bool findFirst) {
  int left = 0;
  int right = arr.length - 1;
  int result = -1;

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

    if (arr[mid] == target) {
      result = mid;
      if (findFirst) {
        right = mid - 1;  // Search left for first occurrence
      } else {
        left = mid + 1;   // Search right for last occurrence
      }
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return result;
}

void main() {
  List<int> nums = [1, 2, 3, 3, 3, 3, 4, 5];
  print(findFirstAndLastUnified(nums, 3));  // [2, 5]
}

Advantage: Less code duplication Time: O(log n), Space: O(1)

Approach 4: Return Range Size

Alternative: return [first, count] instead of [first, last].

dartCopy
List<int> findFirstAndCount(List<int> arr, int target) {
  int first = findFirst(arr, target);

  if (first == -1) return [-1, 0];

  int last = findLast(arr, target);
  int count = last - first + 1;

  return [first, count];
}

void main() {
  List<int> nums = [1, 2, 3, 3, 3, 4];
  print(findFirstAndCount(nums, 3));  // [2, 3] = starts at 2, count is 3
}

Use case: Frequency counting, statistics

Complete Solution Class

Production-ready implementation with all features.

dartCopy
class SearchRange {
  /// Find [first, last] indices of target
  static List<int> find(List<int> arr, int target) {
    int first = _findBound(arr, target, true);
    if (first == -1) return [-1, -1];

    int last = _findBound(arr, target, false);
    return [first, last];
  }

  /// Find first occurrence only
  static int findFirst(List<int> arr, int target) {
    return _findBound(arr, target, true);
  }

  /// Find last occurrence only
  static int findLast(List<int> arr, int target) {
    return _findBound(arr, target, false);
  }

  /// Count occurrences
  static int count(List<int> arr, int target) {
    int first = _findBound(arr, target, true);
    if (first == -1) return 0;

    int last = _findBound(arr, target, false);
    return last - first + 1;
  }

  /// Find range with validation
  static List<int> findSafe(List<int>? arr, int target) {
    if (arr == null || arr.isEmpty) return [-1, -1];
    return find(arr, target);
  }

  /// Internal: Unified bound search
  static int _findBound(List<int> arr, int target, bool findFirst) {
    int left = 0;
    int right = arr.length - 1;
    int result = -1;

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

      if (arr[mid] == target) {
        result = mid;
        if (findFirst) {
          right = mid - 1;
        } else {
          left = mid + 1;
        }
      } else if (arr[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return result;
  }
}

Comparison Table

For interviews: Use Two Binary Searches or Unified Function

Visualization Example

Finding range of

8

[5, 7, 7, 8, 8, 8, 8, 10]

dartCopy
void visualize() {
  List<int> arr = [5, 7, 7, 8, 8, 8, 8, 10];
  int target = 8;

  print('Finding first occurrence of $target:');
  int left = 0, right = arr.length - 1;
  int first = -1;
  int step = 1;

  while (left <= right) {
    int mid = left + (right - left) ~/ 2;
    print('Step $step: left=$left, mid=$mid, right=$right, arr[$mid]=${arr[mid]}');

    if (arr[mid] == target) {
      first = mid;
      print('  → Found at $mid, search left for earlier occurrence');
      right = mid - 1;
    } else if (arr[mid] < target) {
      print('  → ${arr[mid]} < $target, search right');
      left = mid + 1;
    } else {
      print('  → ${arr[mid]} > $target, search left');
      right = mid - 1;
    }
    step++;
  }

  print('First occurrence at index: $first
');

  // Similar for last...
}

// Output:
// Finding first occurrence of 8:
// Step 1: left=0, mid=3, right=7, arr[3]=8
//   → Found at 3, search left for earlier occurrence
// Step 2: left=0, mid=1, right=2, arr[1]=7
//   → 7 < 8, search right
// Step 3: left=2, mid=2, right=2, arr[2]=7
//   → 7 < 8, search right
// First occurrence at index: 3

Edge Cases

dartCopy
void testEdgeCases() {
  // Empty array
  assert(SearchRange.find([], 5) == [-1, -1]);

  // Single element - found
  assert(SearchRange.find([5], 5) == [0, 0]);

  // Single element - not found
  assert(SearchRange.find([5], 3) == [-1, -1]);

  // All same elements
  assert(SearchRange.find([3, 3, 3, 3, 3], 3) == [0, 4]);

  // No duplicates
  assert(SearchRange.find([1, 2, 3, 4, 5], 3) == [2, 2]);

  // Target at start
  assert(SearchRange.find([1, 1, 2, 3], 1) == [0, 1]);

  // Target at end
  assert(SearchRange.find([1, 2, 3, 3], 3) == [2, 3]);

  // Not found - too small
  assert(SearchRange.find([10, 20, 30], 5) == [-1, -1]);

  // Not found - too large
  assert(SearchRange.find([10, 20, 30], 40) == [-1, -1]);

  // Count occurrences
  assert(SearchRange.count([1, 2, 3, 3, 3, 4], 3) == 3);
}

Best Practices

1. Always Use O(log n) Approach in Interviews

dartCopy
// ✅ Good - O(log n) guaranteed
List<int> range = SearchRange.find(arr, target);

// ❌ Bad - O(n) worst case
List<int> range = findFirstAndLastLinear(arr, target);

2. Validate Input

dartCopy
// ✅ Handle edge cases
List<int> findRange(List<int>? arr, int target) {
  if (arr == null || arr.isEmpty) return [-1, -1];
  return SearchRange.find(arr, target);
}

3. Return Early if First Not Found

dartCopy
// ✅ Efficient - don't search for last if first not found
int first = findFirst(arr, target);
if (first == -1) return [-1, -1];
int last = findLast(arr, target);

4. Consider Alternative Return Formats

dartCopy
// Option 1: [first, last]
List<int> range = [2, 5];

// Option 2: [first, count]
List<int> range = [2, 4];  // starts at 2, 4 occurrences

// Option 3: Range object
class Range {
  final int start;
  final int end;
  int get count => end - start + 1;
}

Interview Tips

Common Interview Questions:

Q: "What's the time complexity?"

• O(log n) - two binary searches
• NOT O(n) - that's the naive approach

Q: "Can you do it in one pass?"

• No, you need separate searches for first and last
• One search with linear expansion is O(n) worst case

Q: "What if there are no duplicates?"

• Still works, first == last
• Returns [index, index] if found

Q: "How does this differ from standard binary search?"

• Standard: stops when found
• This: continues searching after finding to locate bounds

Follow-up Questions:

• "Find count without finding last?" → Use binary search for
  textCopy

  target

  and
  textCopy

  target+1

• "Works for descending array?" → Yes, reverse comparison logic
• "Find range in 2D matrix?" → Apply to each row or flatten

What to Explain:

1. Why we need two searches (first and last)
2. Why we update
   textCopy

   right = mid - 1

   when finding first
3. Why we update
   textCopy

   left = mid + 1

   when finding last
4. Why this is better than linear expansion

Red Flags to Avoid:

• Using linear expansion in production code ❌
• Not handling empty array ❌
• Forgetting to check if first is -1 ❌
• Confusing first/last search logic ❌

Pro Tips:

• Draw the array and show pointer movement
• Explain with an example containing duplicates
• Mention this is used in database range queries
• Compare with
  textCopy

  Collections.binarySearch()

  in Java

Resources

• Search Range - LeetCode
• Binary Search Variants
• Dart Binary Search