findFirstAndLastPositionOfElementInSortedArray.ts

/*

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 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

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

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

*/

function searchRange(nums: number[], target: number): number[] {
	let left = 0;
	let right = nums.length - 1;
	let mid = Math.floor((left + right) / 2);

	// Find the left position
	while (left <= right) {
		if (target <= nums[mid]) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}

		mid = Math.floor((left + right) / 2);
	}
	const leftPos = left;

	left = 0;
	right = nums.length - 1;
	mid = Math.floor((left + right) / 2);

	// Find the right position
	while (left <= right) {
		if (target < nums[mid]) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}

		mid = Math.floor((left + right) / 2);
	}
	const rightPos = right;

	return nums[leftPos] !== target ? [-1, -1] : [leftPos, rightPos];
}

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

console.log(searchRange([1, 1, 2, 2, 3, 3], 1));