0034. Find First and Last Position of Element in Sorted Array

題目

題目大意

解題思路

Big O

• 時間複雜 : O(log(n))
• 空間複雜 : O(1)

來源

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

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0034.Find-First-and-Last-Position-of-Element-in-Sorted-Array/main.go

package findfirstandlastpositionofelementinsortedarray

// 時間複雜 O(log(n)), 空間複雜 O(1)
func searchRange(nums []int, target int) []int {
    result := []int{}

    // first index
    left, right := 0, len(nums)-1
    for left < right {
        mid := int(uint(left+right) >> 1) // [0,1] => 0
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            right = mid
        }
    }
    if left == right && nums[left] == target {
        result = append(result, left)
    } else {
        result = append(result, -1)
    }

    // last index
    left, right = 0, len(nums)-1
    for left < right {
        mid := int(uint(left+right+1) >> 1) // [0,1] => 1
        if nums[mid] < target {
            left = mid + 1
        } else if nums[mid] > target {
            right = mid - 1
        } else {
            left = mid
        }
    }
    if left == right && nums[left] == target {
        result = append(result, left)
    } else {
        result = append(result, -1)
    }
    return result
}

Benchmark