Leetcode 34.Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you 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]

Constraints:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums is a non-decreasing array.
  • -109 <= target <= 109
//Java
import java.util.Arrays;

class SearchRange {
public static void main(String[] args) {
Solution sl = new Solution();
System.out.println(Arrays.toString(sl.searchRange(new int[] { 1, 2, 3, 4, 5, 7, 7, 7, 7, 8 }, 7)));
}
}
class Solution {
public int[] searchRange(int[] nums, int target) {
return new int[] { findFirst(nums, target), findLast(nums, target) };
}

public int findFirst(int[] nums, int target) {
int index = -1;

int start = 0;
int end = nums.length - 1;

while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
if (nums[mid] == target)
index = mid;
}

return index;
}

public int findLast(int[] nums, int target) {
int index = -1;

int start = 0;
int end = nums.length - 1;

while (start <= end) {
int mid = start + (end - start) / 2;
if (nums[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
if (nums[mid] == target)
index = mid;
}

return index;
}
}
//Javascript
var searchRange = function(nums, target) {
return [findFirst(nums,target),findLast(nums,target)];
};

var findFirst = function(nums, target) {
let index = -1;

let start = 0;
let end = nums.length - 1;

while (start <= end) {
let mid = start + Math.floor((end - start) / 2);
if (nums[mid] >= target) {
end = mid - 1;
} else {
start = mid + 1;
}
if (nums[mid] == target)
index = mid;
}

return index;
};

var findLast = function(nums, target) {
let index = -1;

let start = 0;
let end = nums.length - 1;

while (start <= end) {
let mid = start + Math.floor((end - start) / 2);
if (nums[mid] <= target) {
start = mid + 1;
} else {
end = mid - 1;
}
if (nums[mid] == target)
index = mid;
}

return index;
};

console.log(searchRange([5,7,7,8,8,10],8))

student at Flatiron School