-
Notifications
You must be signed in to change notification settings - Fork 119
/
Copy pathFind First and Last Position of Element in Sorted Array.js
50 lines (46 loc) · 1.68 KB
/
Find First and Last Position of Element in Sorted Array.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
var searchRange = function(nums, target) {
if (nums.length === 1) return nums[0] === target ? [0, 0] : [-1, -1];
const findFirstInstance = (left, right) => {
if (left === right) return left;
var pivot;
while (left < right) {
if (left === pivot) left += 1;
pivot = Math.floor((left + right) / 2);
if (nums[pivot] === target) {
if (nums[pivot - 1] !== target) return pivot;
return findFirstInstance(left, pivot - 1);
}
if (nums[pivot] > target) right = pivot;
else left = pivot;
}
}
const findLastInstance = (left, right) => {
if (left === right) return left;
var pivot;
while (left < right) {
if (left === pivot) left += 1;
pivot = Math.floor((left + right) / 2);
if (nums[pivot] === target) {
if (nums[pivot + 1] !== target) return pivot;
return findLastInstance(pivot + 1, right);
}
if (nums[pivot] > target) right = pivot;
else left = pivot;
}
}
var left = 0,
right = nums.length - 1,
pivot;
while (left < right) {
if (left === pivot) left += 1;
pivot = Math.floor((left + right) / 2);
if (nums[pivot] === target) {
var first = nums[pivot - 1] !== target ? pivot : findFirstInstance(left, pivot - 1);
var last = nums[pivot + 1] !== target ? pivot : findLastInstance(pivot + 1, right);
return [first, last];
}
if (nums[pivot] > target) right = pivot;
else left = pivot;
}
return [-1, -1];
};