在排序數(shù)組中查找元素的第一個(gè)和最后一個(gè)位置

題目描述：給定一個(gè)按照升序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

進(jìn)階：

• 你可以設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 O(log n) 的算法解決此問題嗎？

示例說明請(qǐng)見LeetCode官網(wǎng)。

來源：力扣（LeetCode） ??

鏈接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/ ??

著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解法一：二分查找、遞歸

用left和right記錄開始位置和結(jié)束位置，用二分查找法查找target在nums中的位置，從0到nums.length-1分別記為low和high，mid表示中間值，具體過程如下：

• 計(jì)算mid為low和high的中間值；

• 如果mid的值和target相等，則判斷mid左邊的元素是否跟target相等，如果相等，則遞歸查找開始位置，從low到mid-1查找，如果不相等，則left為mid；判斷mid右邊的元素是否跟target相等，如果相等，則遞歸查找結(jié)束位置，從mid+1到high查找，如果不相等，則right為mid；

• 如果mid的值大于target，則high更新為mid-1；

• 如果mid的值小于target，則low更新為mid+1。

查找完成后返回left和right即為最終結(jié)果。

【每日寄語】 陽春三月，萬物復(fù)蘇，愿所有美好如期而至。