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

題目

題目大意

解題思路

Big O

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

來源

解答

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



© Kimi Tsai all right reserved.            Updated : 2024-05-06 09:36:37

results matching ""

    No results matching ""