First and Last Occurrence - Binary Search (C++)

editorial
1

Problem: Find first and last index of x in a sorted array.

Approach: Binary Search (twice)

Code (C++):

// First Occurrence
int first(vector& nums, int x) {
int lo = 0, hi = nums.size() - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == x) { ans = mid; hi = mid - 1; }
else if (nums[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}

// Last Occurrence
int last(vector& nums, int x) {
int lo = 0, hi = nums.size() - 1, ans = -1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (nums[mid] == x) { ans = mid; lo = mid + 1; }
else if (nums[mid] < x) lo = mid + 1;
else hi = mid - 1;
}
return ans;
}

Example:
nums = [2,4,4,4,6,8], x = 4
First = index 1, Last = index 3

Time: O(log n) | Space: O(1)