在已排序數組中查找元素的第一個和最后一個位置

給定一個按照升序排列的整數數組`nums`，和一個目標值`target`。要求找出給定目標值在數組中的開始位置和結束位置。時間復雜度為O(logn)。解決方案我們可以使用二分查找來解決這個問題。首先，

給定一個按照升序排列的整數數組`nums`，和一個目標值`target`。要求找出給定目標值在數組中的開始位置和結束位置。時間復雜度為O(logn)。

解決方案

我們可以使用二分查找來解決這個問題。首先，我們需要編寫一個函數，通過二分查找獲取一個指定值在有序數組中第一次出現的位置。如果沒有找到該元素，則返回-1。其偽代碼如下：

```

function findFirstOccurrence(nums, target):

left 0

right nums.length - 1

while left < right:

mid (left right) / 2

if nums[mid] target and (mid 0 or nums[mid-1] ! target):

return mid

elif nums[mid] < target:

left mid 1

else:

right mid - 1

return -1

```

接下來，我們再編寫一個函數，通過二分查找獲取一個指定值在有序數組中最后出現的位置。如果沒有找到該元素，則返回-1。其偽代碼如下：

```

function findLastOccurrence(nums, target):

left 0

right nums.length - 1

while left < right:

mid (left right) / 2

if nums[mid] target and (mid nums.length-1 or nums[mid 1] ! target):

return mid

elif nums[mid] > target:

right mid - 1

else:

left mid 1

return -1

```

接下來，我們將上述兩個二分查找方法結合起來，編寫一個函數來獲取一個元素在排序數組中第一次和最后一次出現的位置。其偽代碼如下：

```

function searchRange(nums, target):

first findFirstOccurrence(nums, target)

last findLastOccurrence(nums, target)

return [first, last]

```

測試方法

為了驗證我們的解決方案是否正確，我們需要編寫一些測試方法。以下是一個簡單的測試方法：

```

function test():

nums [1, 2, 2, 3, 4, 5, 5, 5, 6]

target 5

result searchRange(nums, target)

if result [5, 7]:

print("Test Passed")

else:

print("Test Failed")

test()

```

運行測試方法

運行上述測試方法，并觀察控制臺輸出。如果輸出符合預期，則本地測試通過。

提交算法

在完成本地測試之后，可以將算法提交到相應的平臺進行測試。如果經過平臺測試也通過了，那么我們的解決方案就是正確的。

通過以上步驟，我們可以在已排序數組中高效地查找元素的第一個和最后一個位置。這種方法的時間復雜度為O(logn)，相比于線性查找的O(n)要更加高效。