First and last position of a value

def search_range(nums, target):
    def first_at_least(x):             # first index with nums[i] >= x, or len(nums)
        lo, hi = 0, len(nums)
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] >= x:
                hi = mid
            else:
                lo = mid + 1
        return lo

    first = first_at_least(target)
    if first == len(nums) or nums[first] != target:
        return [-1, -1]
    return [first, first_at_least(target + 1) - 1]   # integers: "> target" is ">= target + 1"

#include <vector>

// first index with nums[i] >= x, or nums.size()
static int firstAtLeast(const std::vector<int>& nums, long long x) {
    int lo = 0, hi = (int)nums.size();
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] >= x) hi = mid; else lo = mid + 1;
    }
    return lo;
}

std::vector<int> solve(const std::vector<int>& nums, int target) {
    int first = firstAtLeast(nums, target);
    if (first == (int)nums.size() || nums[first] != target) return {-1, -1};
    return {first, firstAtLeast(nums, (long long)target + 1) - 1};   // target + 1 cannot overflow
}

class Solution {
    // first index with nums[i] >= x, or nums.length
    private int firstAtLeast(int[] nums, long x) {
        int lo = 0, hi = nums.length;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (nums[mid] >= x) hi = mid; else lo = mid + 1;
        }
        return lo;
    }

    public int[] searchRange(int[] nums, int target) {
        int first = firstAtLeast(nums, target);
        if (first == nums.length || nums[first] != target) return new int[]{-1, -1};
        return new int[]{first, firstAtLeast(nums, (long) target + 1) - 1};
    }
}

function searchRange(nums, target) {
  // first index with nums[i] >= x, or nums.length
  const firstAtLeast = x => {
    let lo = 0, hi = nums.length;
    while (lo < hi) {
      const mid = lo + ((hi - lo) >> 1);
      if (nums[mid] >= x) hi = mid; else lo = mid + 1;
    }
    return lo;
  };
  const first = firstAtLeast(target);
  if (first === nums.length || nums[first] !== target) return [-1, -1];
  return [first, firstAtLeast(target + 1) - 1];
}

fn solve(nums: &[i64], target: i64) -> Vec<i64> {
    // partition_point returns the first index where the predicate turns false
    let first = nums.partition_point(|&x| x < target);
    if first == nums.len() || nums[first] != target {
        return vec![-1, -1];
    }
    let end = nums.partition_point(|&x| x <= target);
    vec![first as i64, end as i64 - 1]
}

import Data.Array

solve :: [Int] -> Int -> [Int]
solve nums target
  | first == n || a ! first /= target = [-1, -1]
  | otherwise = [first, firstAtLeast (target + 1) - 1]
  where
    n = length nums
    a = listArray (0, n - 1) nums
    first = firstAtLeast target
    -- first index with a[i] >= x, or n
    firstAtLeast x = go 0 n
      where
        go lo hi
          | lo >= hi     = lo
          | a ! mid >= x = go lo mid
          | otherwise    = go (mid + 1) hi
          where mid = lo + (hi - lo) `div` 2