:orphan:

Find First And Last Position Of Element In Sorted Array
=======================================================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/

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.

 

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

.. highlight:: python

Pattern
-------
Array, Binary Search

Solution
--------
First perform binary search to find the ``index`` of any ``target`` in the
array. Divide ``nums`` into 2 halves: left of ``index`` and right of ``index``.
If we perform binary search again on the left half, we get a new index
``right`` for a ``target`` element in ``nums`` left of ``index``. If we cannot
find ``target``, then ``index`` must be the left-most position of any ``target``
value in ``nums``. Thus we recursively perform binary search using ``left``
until we can no longer find ``target`` and use the previous ``left`` value as
the lower bound. Similarly, we recursively perform binary search on the right
half until we can no longer find target.

Code
----

.. literalinclude:: ../problems/medium/find-first-and-last-position-of-element-in-sorted-array/find_first_and_last_position_of_element_in_sorted_array__approach_1.py
    :language: python
    :lines: 11-

Test
----
>>> from find_first_and_last_position_of_element_in_sorted_array__approach_1 import searchRange
>>> searchRange([5, 7, 7, 8, 8, 10], 8)
[3, 4]
>>> searchRange([5, 7, 7, 8, 8, 10], 6)
[-1, -1]
>>> searchRange([], 0)
[-1, -1]

Complexity
----------
| :math:`n` is the length of the input array
| Time: :math:`O(\log n)` — repeated binary search
| Auxiliary Space: :math:`O(1)` — constant extra space

.. autofunction:: find_first_and_last_position_of_element_in_sorted_array__approach_1.searchRange

.. autofunction:: find_first_and_last_position_of_element_in_sorted_array__approach_1.binary_search