Solving a Leetcode problem daily — Day 10 | Find first and last position in sorted array
Tags: 34, binarysearch, leetcode, sort
Published: 2024-05-11 03:17:37

{% embed https://medium.com/@subhradeep_saha/solving-a-leetcode-problem-daily-day-10-find-first-and-last-position-in-sorted-array-0ca712b20f58 %}

---

Here is the Leetcode problem link - [https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/description/)

---


# **Problem Statement**

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.

```cpp
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 <= 10^5`
    
* `-10^9 <= nums[i] <= 10^9`
    
* `nums` is a non-decreasing array.
    
* `-10^9 <= target <= 10^9`
    

# **High-Level Approach**

## **Binary search to the rescue**

The brute force solution entails iterating through each item in the input array to determine the first and last indices of the specified target.  
However, since the input is in non-decreasing order, we can leverage binary search to take advantage of this characteristic and significantly reduce the time complexity to a logarithmic scale.

## **How are we finding the indices?**

The first index corresponds to either the beginning of the array or the position where the previous number is different from the target. Likewise, the last index corresponds to either the end of the array or the position where the next number is different from the target.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/5ckt6rp8460njylyandl.png)

In cases where the `target` is not present in the input array, both indices’ positions are returned as -1.

# **Code Implementation in C++**

```cpp
class Solution {
public:
  int findIdx(vector<int>& nums, int target, bool firstIdxSearch) {
    int l = 0, h = nums.size() - 1;
    while (l <= h) {
      int m = l + (h - l) / 2;
      if (nums[m] > target) {
        h = m - 1;
      } 
      else if (nums[m] < target) {
        l = m + 1;
      } 
      else {
        if (!firstIdxSearch) {
          // Find last occurrence
          if ((m == nums.size() - 1) || (nums[m + 1] != target)) {
            return m;
          }
          l = m + 1;
        } 
        else {
          // Find first occurrence
          if (!m || (nums[m - 1] != target)) {
            return m;
          }
          h = m - 1;
        }
      }
    }
    return -1;
  }
  vector<int> searchRange(vector<int>& nums, int target) {
      int firstIdx = findIdx(nums, target, true);
      if (firstIdx == -1) {
        return {-1, -1};
      }
      return {firstIdx, findIdx(nums, target, false)};
  }
};
```

# **Breakdown of the Code**

`findIdx` **Function:** This util function takes three arguments:

* `nums`: The sorted array.
    
* `target`: The value to search for.
    
* `firstIdxSearch`: A boolean flag indicating whether to find the first or last occurrence of the target.
    

**Binary Search Loop:** The core logic resides within a `while` loop that continues as long as `l` (lower bound) is less than or equal to `h` (upper bound).

* Inside the loop, `m` (middle index) is calculated.
    
* The comparison between `nums[m]` and `target` determines the search direction:
    

\=&gt; If `nums[m] > target`, the target is in the lower half, so we update `h` to `m-1`.

\=&gt; If `nums[m] < target`, the target is in the upper half, so we update `l` to `m+1`.

\=&gt; If `nums[m] == target`, we've found a potential occurrence. The logic then diverges based on the `firstIdx` flag:

\===&gt; If `firstIdxSearch` is `true` (finding first occurrence), we check if this is truly the first by looking at `nums[m-1]` or is it at the beginning of the array. If not, we need to search in the left half (`h = m-1`).

\===&gt; Else, we check if this is the last by looking at `nums[m+1]` or is it at the end of the array. If not, we need to search in the right half (`l = m+1`).

**Returning the Result:**

* If the loop completes without finding the target (`l` becomes greater than `h`), the function returns `-1`.
    
* Otherwise, the function returns the index (`m`) of the found target occurrence, depending on whether it's the first or last based on the `firstIdxSearch` flag.
    

# **Dry Run with a Test Case**

Let’s perform a dry run on the code using the example `nums = [5,7,7,8,8,10]` and `target = 8`:

## **Searching for First Occurrence (firstIdxSearch = true):**

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i56pl28c2qs3qczq9dno.png)
**Iteration 1:** `l` is set to 0, `h` is set to 5, and `m` is calculated as 2 (middle element):

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gnc1sq6ec686694duhyt.png)

Since `nums[m] < target`, we update `l = m+1`:


**Iteration 2:** Updated `l = 3, h = 5` and `m` is calculated to be 4:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cvci6o1yijk150zgr54n.png)

Now, `nums[m] == target` and `nums[m-1] == target`. So we update `h` as `m — 1`:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ab8n1xqsqd69c9bt29jv.png)

**Iteration 3**: Updated `l = 3, h = 3` and `m` is calculated to be 3 as well:



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/egv4jxi6qn62bvdux0pj.png)
Now, `nums[m] == target` and `nums[m-1] != target`, so we return m as the `firstIdx`.

## **Inside the main searchRange() function**

After `firstIdx` is calculated to be not equal to -1, we proceed to again use the same `findIdx()` function to find the `lastIdx` of the target.

## **Searching for Last Occurrence (**`firstIdxSearch` **= false):**

We call `findIdx()` again but now with the boolean `firstIdxSearch` set to `false` to find the last occurrence.

**Iteration 1**:`l` is set to 0, `h` is set to 5, and `m` is calculated as 2 (middle element):

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dpe0s1sb65qvchpas66t.png)


Since `nums[m] < target`, we update `l = m+1`:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jy8lk3k7xez3s2y4w7t5.png)


**Iteration 2**: Updated `l = 3, h = 5` and `m` is calculated to be 4:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jthcaze5vs5t72snb4rm.png)

Now, `nums[m] == target` and `nums[m+1] != target`, so we return m as the lastIdx of the target.

Finally, we return `{firstIdx = 3, lastIdx = 4}` from the main function as the answer.

# **Complexity Analysis**

* **Time Complexity:** `O(log n)`. The `findIdx()` function divides the search space into half with every iteration leading to a logarithmic time complexity in terms of n(the size of the input array).
    
* **Space Complexity:** `O(1)`. The code utilizes a constant amount of extra space for variables like `l`, `h`, and `m`, regardless of the array size (`n`).
    

# **Possible Improvements in the code**

After the first `findIdx()` call, we obtain the index where the `target` is first found. Subsequently, for the second `findIdx()` call aimed at locating the last occurrence of the `target`, we can directly start the lower bound `l` as the output of the first `findIdx()` call instead of starting from 0. This is because we are certain that the target’s last occurrence cannot precede its first occurrence.

In the above example, when we call the `findIdx()` function to locate the last occurrence of the `target` (in this case, 8), we can optimize by using the output of the first call. This allows us to start processing directly from `l = 3` (instead of `l = 0`) for the 2nd `findIdx()` function, thereby reducing the number of iterations required in the while loop.

# **Real-World Applications**

* **Log File Search and Analysis**: ystem logs often contain timestamped records of events or errors. These logs can be sorted chronologically. When troubleshooting issues or analyzing system behavior within a specific timeframe (e.g., identifying errors that occurred between 10:00 AM and 11:00 AM), binary search can be used to efficiently locate the relevant log entries within the sorted time range.
    
* **Financial Data Analysis and Trend Identification**: Financial analysts might analyze historical stock prices which are often sorted chronologically. To identify periods where stock prices remained within a specific range (e.g., identifying days when a stock price stayed between $100 and $105), binary search can be applied to efficiently locate the relevant date ranges within the sorted price data.
    

# **Conclusion**

This blog post delves into the problem of locating the initial and concluding positions of a target value within a sorted array. We explored the benefits of employing binary search for efficient searching, offer a comprehensive breakdown of the C++ code implementation, evaluated the time and space complexity, and investigated real-world applications of the given problem.

# **References**

* [https://developers.cloudflare.com/logs/](https://developers.cloudflare.com/logs/)
    
* [https://www.quantconnect.com/learning/articles/introduction-to-financial-python](https://www.quantconnect.com/learning/articles/introduction-to-financial-python)
    
* Diagrams are made using [Canva](https://www.canva.com/join/qsx-lqt-tpb)
    
* Cover Photo by [Markus Winkler](https://unsplash.com/@markuswinkler?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash) on [Unsplash](https://unsplash.com/photos/round-grey-and-black-magnifying-glass-BvlxNyjnIzg?utm_content=creditCopyText&utm_medium=referral&utm_source=unsplash)
    

# **What next?**

If you’re intrigued by binary search algorithms, do check out my other posts where I delve into fascinating use cases that are solved using binary search.

* [First Bad Version](https://dev.to/subhradeep__saha/solving-a-leetcode-problem-daily-day-9-first-bad-version-2dk5)
    
* [Sqrt(x)](https://dev.to/subhradeep__saha/solving-a-leetcode-problem-daily-day-8-sqrtx-4p8p)
    

---

Thank you for reading throughout! If you found this post insightful, please show your appreciation by liking this post and sharing it. Don’t forget to follow me for more engaging content like this. Your feedback is valuable, so please feel free to comment or reach out to me with any thoughts or suggestions.

Happy reading and happy coding!