9.10.2023
34. Find First and Last Position of Element in Sorted Array medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/364
Problem TLDR
Binary Search range
Intuition
Just write a Binary Search
Approach
For simpler code:
use inclusive
lo
andhi
check the last condition
lo == hi
always move the borders
lo = mid + 1
,hi = mid - 1
always write the found result
if (nums[mid] == target)
to understand which border to move, consider this thought:
if this position is definitely less than target, we can drop it and all that less than it
Complexity
Time complexity:
O(log(n))Space complexity:
O(1)
Code
fun searchRange(nums: IntArray, target: Int): IntArray {
var from = -1
var lo = 0
var hi = nums.lastIndex
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
if (nums[mid] == target) from = min(max(from, nums.size), mid)
if (nums[mid] < target) lo = mid + 1
else hi = mid - 1
}
var to = from
lo = maxOf(0, from)
hi = nums.lastIndex
while (lo <= hi) {
val mid = lo + (hi - lo) / 2
if (nums[mid] == target) to = max(min(-1, to), mid)
if (nums[mid] <= target) lo = mid + 1
else hi = mid - 1
}
return intArrayOf(from, to)
}