find-first-and-last-position-of-element-in-sorted-array

malipramod · malipramod · commit bb549a618f0c · 2019-07-26T16:44:58.000+05:30
diff --git a/medium/0043 find-first-and-last-position-of-element-in-sorted-array/find-first-and-last-position-of-element-in-sorted-array.js b/medium/0043 find-first-and-last-position-of-element-in-sorted-array/find-first-and-last-position-of-element-in-sorted-array.js
@@ -0,0 +1,30 @@
+/**
+ * @param {number[]} nums
+ * @param {number} target
+ * @return {number[]}
+ */
+var searchRange = function (nums, target) {
+    let range = [-1, -1];
+    let left = extremeInsertionIndex(nums, target, true);
+    if(left == nums.length || nums[left] != target){
+        return range;
+    }
+    range[0] = left;
+    range[1] = extremeInsertionIndex(nums, target, false) - 1;
+    return range;
+};
+
+const extremeInsertionIndex = function (nums, target, left) {
+    let low = 0, high = nums.length;
+    while (low < high) {
+        let middle = Math.floor((low + high) / 2);
+        if (nums[middle] > target || (left && target == nums[middle])) {
+            high = middle;
+        } else {
+            low = middle + 1;
+        }
+    }
+    return low;
+}
+
+console.log(searchRange([5,7,7,8,8,10],5))
diff --git a/medium/0043 find-first-and-last-position-of-element-in-sorted-array/readme.md b/medium/0043 find-first-and-last-position-of-element-in-sorted-array/readme.md
@@ -0,0 +1,23 @@
+# 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.
+
+Your algorithm's runtime complexity must be in the order of O(log n).
+
+If the target is not found in the array, return [-1, -1].
+
+## 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]
+
+## More Info
+
+<https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/>
