Find fisrt and last position of element in sorted array

Array Binary Search

48.4% acceptance

Jan 12, 2026

23139

634

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn search_range(nums: Vec<i32>, target: i32) -> Vec<i32> {
    if nums.is_empty() {
      return vec![-1, -1];
    }
    
    let left = Self::find_left(&nums, target);
    if left == -1 {
      return vec![-1, -1];
    }
    
    let right = Self::find_right(&nums, target);
    vec![left, right]
  }
  
  fn find_left(nums: &Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;
    let mut result = -1;
    
    while left <= right {
      let mid = left + (right - left) / 2;
      
      if nums[mid] == target {
        result = mid as i32;
        if mid == 0 {
          break;
        }
        right = mid - 1;
      } else if nums[mid] < target {
        left = mid + 1;
      } else {
        if mid == 0 {
          break;
        }
        right = mid - 1;
      }
    }
    
    result
  }
  
  fn find_right(nums: &Vec<i32>, target: i32) -> i32 {
    let mut left = 0;
    let mut right = nums.len() - 1;
    let mut result = -1;
    
    while left <= right {
      let mid = left + (right - left) / 2;
      
      if nums[mid] == target {
        result = mid as i32;
        left = mid + 1;
      } else if nums[mid] < target {
        left = mid + 1;
      } else {
        if mid == 0 {
          break;
        }
        right = mid - 1;
      }
    }
    
    result
  }
}