Find First And Last Position Of Element In Sorted Array

                                            
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> result = {-1, -1};
        int left = 0;
        int right = nums.size() - 1;
        
        // Find the starting position of target
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (left < nums.size() && nums[left] == target) {
            result[0] = left;
        } else {
            return result;
        }
        
        // Find the ending position of target
        right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        result[1] = right;
        
        return result;
    }
};

                                            
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] result = new int[]{-1, -1};
        
        // Find the starting position
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        if (left < nums.length && nums[left] == target) {
            result[0] = left;
        }
        
        // Find the ending position
        left = 0;
        right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        if (right >= 0 && nums[right] == target) {
            result[1] = right;
        }
        
        return result;
    }
}

                                            
class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        def binary_search_left(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] < target:
                    left = mid + 1
                else:
                    right = mid - 1
            return left
        
        def binary_search_right(nums, target):
            left, right = 0, len(nums) - 1
            while left <= right:
                mid = left + (right - left) // 2
                if nums[mid] <= target:
                    left = mid + 1
                else:
                    right = mid - 1
            return right
        
        left_idx = binary_search_left(nums, target)
        right_idx = binary_search_right(nums, target)
        
        if left_idx <= right_idx:
            return [left_idx, right_idx]
        else:
            return [-1, -1]

                                            
/**
 * Note: The returned array must be malloced, assume caller calls free
().
 */
int* searchRange(int* nums, int numsSize, int target, int* returnSize) 
{
    // find the leftmost index of the target
    int left = 0, right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    int startIndex = (left < numsSize && nums[left] == target) ? left : -1;

    // find the rightmost index of the target
    left = 0;
    right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    int endIndex = (right >= 0 && nums[right] == target) ? right : -1;

    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = startIndex;
    result[1] = endIndex;

    *returnSize = 2;
    return result;
}

                                            
public class Solution {
    public int[] SearchRange(int[] nums, int target) {
        int[] result = new int[] { -1, -1 };

        if (nums == null || nums.Length == 0) {
            return result;
        }

        int left = findLeftIndex(nums, target);
        int right = findRightIndex(nums, target);

        result[0] = left;
        result[1] = right;

        return result;
    }

    private int findLeftIndex(int[] nums, int target) {
        int index = -1;
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                index = mid;
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return index;
    }

    private int findRightIndex(int[] nums, int target) {
        int index = -1;
        int left = 0;
        int right = nums.Length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (nums[mid] == target) {
                index = mid;
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return index;
    }
}

                                            
function searchRange(nums: number[], target: number): number[] {
    let result = [-1, -1];
    
    let left = 0;
    let right = nums.length - 1;
    
    // Find the leftmost index
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            result[0] = mid;
            right = mid - 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    // Find the rightmost index
    left = 0;
    right = nums.length - 1;
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] === target) {
            result[1] = mid;
            left = mid + 1;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};

                                            
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function searchRange($nums, $target) {
        $start = -1;
        $end = -1;
        
        $left = 0;
        $right = count($nums) - 1;

        while ($left <= $right) {
            $mid = $left + intdiv(($right - $left), 2);

            if ($nums[$mid] == $target) {
                $start = $mid;
                $end = $mid;

                // Find left boundary
                $left = $mid;
                while ($left > 0 && $nums[$left - 1] == $target) {
                    $left--;
                    $start = $left;
                }

                // Find right boundary
                $right = $mid;
                while ($right < count($nums) - 1 && $nums[$right + 1] == $target) {
                    $right++;
                    $end = $right;
                }

                break;
            } elseif ($nums[$mid] < $target) {
                $left = $mid + 1;
            } else {
                $right = $mid - 1;
            }
        }

        return [$start, $end];
    }
}

                                            
class Solution {
    func searchRange(_ nums: [Int], _ target: Int) -> [Int] {
        guard !nums.isEmpty else {
            return [-1, -1]
        }
        
        // Binary search to find the start position
        var start = -1
        var left = 0
        var right = nums.count - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            if nums[mid] >= target {
                right = mid - 1
            } else {
                left = mid + 1
            }
            if nums[mid] == target {
                start = mid
            }
        }
        
        if start == -1 {
            return [-1, -1]
        }
        
        // Binary search to find the end position
        var end = -1
        left = 0
        right = nums.count - 1
        
        while left <= right {
            let mid = left + (right - left) / 2
            if nums[mid] <= target {
                left = mid + 1
            } else {
                right = mid - 1
            }
            if nums[mid] == target {
                end = mid
            }
        }
        
        return [start, end]
    }
}

                                            
class Solution {
    fun searchRange(nums: IntArray, target: Int): IntArray {
        var left = 0
        var right = nums.size - 1
        var startPos = findStartingPosition(nums, target, left, right)
        var endPos = findEndingPosition(nums, target, left, right)
        return intArrayOf(startPos, endPos)
    }
    
    private fun findStartingPosition(nums: IntArray, target: Int, left: Int, right: Int): Int {
        var start = -1
        var l = left
        var r = right
        while (l <= r) {
            var mid = l + (r - l) / 2
            if (nums[mid] >= target) {
                r = mid - 1
            } else {
                l = mid + 1
            }
            if (nums[mid] == target) {
                start = mid
            }
        }
        return start
    }
    
    private fun findEndingPosition(nums: IntArray, target: Int, left: Int, right: Int): Int {
        var end = -1
        var l = left
        var r = right
        while (l <= r) {
            var mid = l + (r - l) / 2
            if (nums[mid] <= target) {
                l = mid + 1
            } else {
                r = mid - 1
            }
            if (nums[mid] == target) {
                end = mid
            }
        }
        return end
    }
}

                                            
class Solution {
  List<int> searchRange(List<int> nums, int target) {
    if (nums.isEmpty) {
      return [-1, -1];
    }
    
    int findFirst(int target) {
      int left = 0;
      int right = nums.length - 1;
      while (left < right) {
        int mid = left + ((right - left) ~/ 2);
        if (nums[mid] < target) {
          left = mid + 1;
        } else {
          right = mid;
        }
      }
      return nums[left] == target ? left : -1;
    }
    
    int findLast(int target) {
      int left = 0;
      int right = nums.length - 1;
      while (left < right) {
        int mid = left + ((right - left + 1) ~/ 2);
        if (nums[mid] > target) {
          right = mid - 1;
        } else {
          left = mid;
        }
      }
      return nums[left] == target ? left : -1;
    }
    
    return [findFirst(target), findLast(target)];
  }
}

                                            
func searchRange(nums []int, target int) []int {
    result := []int{-1, -1}
    
    left := 0
    right := len(nums) - 1
    
    // Find the leftmost target
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            result[0] = mid
            right = mid - 1
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    if result[0] == -1 {
        return result
    }
    
    // Find the rightmost target
    left = result[0]
    right = len(nums) - 1
    
    for left <= right {
        mid := left + (right - left) / 2
        if nums[mid] == target {
            result[1] = mid
            left = mid + 1
        } else if nums[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    
    return result
}

                                            
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def search_range(nums, target)
    left = search_bound(nums, target, true)
    right = search_bound(nums, target, false)
    
    if left < nums.length && nums[left] == target
        [left, right - 1]
    else
        [-1, -1]
    end
end

def search_bound(nums, target, isFirst)
    left = 0
    right = nums.length
    
    while left < right
        mid = left + (right - left) / 2
        
        if nums[mid] > target || (isFirst && nums[mid] >= target)
            right = mid
        else
            left = mid + 1
        end
    end
    
    left
end

                                            
object Solution {
    def searchRange(nums: Array[Int], target: Int): Array[Int] = {
        def binarySearch(nums: Array[Int], target: Int, left: Boolean): Int = {
            var lo = 0
            var hi = nums.length
            while (lo < hi) {
                val mid = (lo + hi) / 2
                if (nums(mid) > target || (left && nums(mid) == target)) {
                    hi = mid
                } else {
                    lo = mid + 1
                }
            }
            lo
        }

        val leftIdx = binarySearch(nums, target, left = true)
        if (leftIdx == nums.length || nums(leftIdx) != target) {
            return Array(-1, -1)
        }
        val rightIdx = binarySearch(nums, target, left = false) - 1
        Array(leftIdx, rightIdx)
    }
}

                                            
impl Solution {
    pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
        if nums.is_empty() { return vec![-1, -1]; }
        
        let left = match nums.binary_search(&target) {
            Ok(mut idx) => {
                while idx > 0 && nums[idx - 1] == target {
                    idx -= 1;
                }
                idx
            },
            _ => return vec![-1, -1],
        };
        
        let right = match nums.binary_search(&target) {
            Ok(mut idx) => {
                while idx < nums.len() - 1 && nums[idx + 1] == target {
                    idx += 1;
                }
                idx
            },
            _ => return vec![-1, -1],
        };
        
        vec![left as i32, right as i32]
    }
}

To solve this coding challenge, we need to find the first and last positions of a specified target value within a given array of integers that is sorted in non-decreasing order. If the target is not present in the array, we should return [-1, -1]. The problem requires that we solve it using an algorithm with O(log n) runtime complexity, which naturally suggests using binary search. The binary search algorithm is efficient for divide-and-conquer problems and performs search operations in logarithmic time complexity.

Explanation

We will approach the problem by applying binary search twice:

To find the leftmost (first) position of the target.
To find the rightmost (last) position of the target.

The idea is to perform a binary search that specifically looks for the first occurrence and another binary search that finds the last occurrence of the target in the array. During the left binary search, when we find the target, we continue searching to the left. Conversely, during the right binary search, when we find the target, we continue searching to the right.

Detailed Steps in Pseudocode

Define a function called
searchRange

that takes
nums

and
target

as parameters .
Create two helper functions:
binary_search_left

and
binary_search_right

.

binary_search_left

will find the leftmost index where the target can be found.

binary_search_right

will find the rightmost index where the target can be found.

Implement the
binary_search_left

function :

* Initialize

left

to 0 and

right

to the length of

nums

- 1.

* While

left

is less than or equal to

right

, calculate

mid

* If

nums[mid]

is less than the target, adjust

left

mid + 1

* Otherwise, adjust

right

mid - 1

* Return

left

after the loop ends.

Implement the
binary_search_right

function :

* Initialize

left

to 0 and

right

to the length of

nums

- 1.

* While

left

is less than or equal to

right

, calculate

mid

* If

nums[mid]

is less than or equal to the target, adjust

left

mid + 1

* Otherwise, adjust

right

mid - 1

* Return

right

after the loop ends.

Call
binary_search_left

and
binary_search_right

to get the positions .
Check if the target is present :

* If

left_idx

is less than or equal to

right_idx

and

nums[left_idx]

equals

target

and

nums[right_idx]

equals

target

, return

[left_idx, right_idx]

* Otherwise, return

[-1, -1]

Here's the pseudocode to solve the challenge:

                                            
# Main function to find the first and last position of the target in the array
function searchRange(nums, target):
    # Binary search to find the leftmost position of the target
    function binary_search_left(nums, target):
        left = 0
        right = length(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left  # This is the leftmost index where target would be

    # Binary search to find the rightmost position of the target
    function binary_search_right(nums, target):
        left = 0
        right = length(nums) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] <= target:
                left = mid + 1
            else:
                right = mid - 1
        return right  # This is the rightmost index where target would be

    # Find the indices using the helper functions
    left_idx = binary_search_left(nums, target)
    right_idx = binary_search_right(nums, target)

    # Verify if the target is within the bounds and positions are correct
    if left_idx <= right_idx and left_idx < length(nums) and nums[left_idx] == target and right_idx < length(nums) and nums[right_idx] == target:
        return [left_idx, right_idx]  # Return the indices where the target starts and ends
    else:
        return [-1, -1]  # Target is not present in the array

This pseudocode provides a step-by-step implementation of the solution, ensuring the detailed use of binary search to maintain the O(log n) runtime complexity as required by the problem.