Leetcode 0034 First Last Position In Sorted Array

Meta Data

Tags

Similar

Problem Statement

  • Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.
  • If target is not found in the array, return [-1, -1].
  • You must write an algorithm with O(log n) runtime complexity.

Example


Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]


Input: nums = [], target = 0
Output: [-1,-1]

Solution Approaches

  • Link
  • Basically Binary search except we are not returning, instead storing the value and running the loop again
  • For First Occurrence
    • when arr[mid] == target then the next value will be on left side, so making hi = mid - 1
  • For Last Occurence
    • when arr[mid] == target then the next value will be on right side, so making lo = mid + 1

vector<int> searchRange(vector<int>& nums, int target) {
	vector<int> ans;

	int lo = 0;
	int hi = nums.size() - 1;
	int mid;
	int pos = -1;

	// first occurence
	while (lo <= hi) {
		mid = lo + (hi - lo) / 2;

		if (nums[mid] == target) {
			pos = mid;
			hi = mid - 1;
		}
		else if (nums[mid] > target) {
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}

	ans.push_back(pos);

	// last occurence
	lo = mid;
	hi = nums.size() - 1;
	pos = -1;
	while (lo <= hi) {
		mid = lo + (hi - lo) / 2;

		if (nums[mid] == target) {
			pos = mid;
			lo = mid + 1;
		}
		else if (nums[mid] > target) {
			hi = mid - 1;
		} else {
			lo = mid + 1;
		}
	}
	ans.push_back(pos);


	return ans;
}


Return to DSA


Notes mentioning this note

There are no notes linking to this note.