Leetcode 0034 First Last Position In Sorted Array

Meta Data

Link

• Find First and Last Position of Element in Sorted Array - LeetCode

Tags

• Binary Search Algorithm

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

O(N) Brute Force Linear Search

• Implementation of classic Linear Search Algorithm

O(Log N) Binary Search

• Link
  • 5 First and Last occurrence of an Element - YouTube by [[ Aditya Verma ]]
• 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