How to Find First and Last Position of Element in Sorted Array

<h1>The Problem</h1> With this article, I will be covering the Find First and Last Position of an Element in a Sorted Array problem. Leetcode describes the problem with the following: <blockquote> Given an array of integers <code>nums</code> sorted in non-decreasing order, find the starting and ending position of a given <code>target</code> value. If <code>target</code> is not found in the array, return <code>[-1, -1]</code>. You must write an algorithm with <code>O(log n)</code> runtime complexity. </blockquote> Example: <blockquote> Input: nums = [5,7,7,8,8,10], target = 8 Output: [3,4] </blockquote> Leetcode ranks this problem as a medium. I think that is an appropriate rating. The solution is feasible but does require some algorithmic understanding. <h2>Naive Approach and Its Limitations</h2> The naive approach for solving this problem would be to scan through the array linearly to find the first and last occurrence of the target value. This involves looping through the array once to find the first occurrence of the target and marking that index as the starting position, then looping through it again to find the last occurrence and marking that as the ending position. While this approach works, it takes <code>O(n)</code> time to solve, which doesn't meet the constraint of <code>O(log n)</code> runtime complexity. Therefore, it would become inefficient when dealing with large datasets. <a href="https://sean-coughlin.medium.com/how-to-find-first-and-last-position-of-element-in-sorted-array-10d8d1f36649">Website</a>