(給算法愛好者加星标，修煉程式設計内功)
來源： 資料結構和算法-山大王wld
問題描述
給定一個按照升序排列的整數數組 nums，和一個目标值 target。找出給定目标值在數組中的開始位置和結束位置。
你的算法時間複雜度必須是 O(log n) 級别。
如果數組中不存在目标值，傳回 [-1, -1]。
示例 1:
輸入: nums = [5,7,7,8,8,10],
target = 8
輸出: [3,4]
示例 2:
輸入: nums = [5,7,7,8,8,10],
target = 6
輸出: [-1,-1]
二分法查找
題中說了是升序的數組，也就是排過序的，對于排過序的數組查找我們
很容易想到的就是二分法。這裡要傳回的是目标值在數組中的開始位置和結束位置，因為相同的數字在排序數組中肯定是挨着的，是以我們通過二分法查到之後，還要往前和往後繼續查找，直到不等于目标值為止。
如果是做Android的并且經常看源碼的可能知道，Android中有個類ArrayMap，他存儲的時候hash值是排過序的，查找的時候也是通過二分法查找，但有可能hash值會有沖突，是以他查找之後也是分别往前和往後繼續查找然後再比較key值，和這題解法很相似。我們來畫個簡圖看一下
比如我們通過二分法查找7，然後還要往他的前面和後面繼續查找，目的是要找到最開始7和最後7的位置，來看下代碼
1
二分法的另一種寫法
二分查找一般我們找到某個值之後會直接傳回。其實我們有時候還可以對二分法進行改造，當查找某個值的時候不直接傳回，而是要繼續查找，直到左右兩個指針相遇為止。像下面這樣，代碼中有詳細的注釋，可以看一下
1
看到這裡可能有的同學靈光乍現，通過二分法能找到target第一次出現的位置，那麼通過二分法能不能找到target最後一次出現的位置。當然也是可以的，代碼在下面給你準備好了
1
總結
以前對二分法的查找，我們是找到之後就傳回。但如果有多個重複的值，我們是沒法确定傳回的是哪個值的下标。今天這裡我們對二分法進行了改造，如果有多個重複的值，你想傳回第一個值或者最後一個值的下标都是可以的。
- EOF -
推薦閱讀 點選标題可跳轉
1、算法題375：在每個樹行中找最大值
2、圖解排序算法：快速排序
3、排序算法：Heap Sort 堆排序與 Top K 問題
覺得本文有幫助？請分享給更多人
關注「算法愛好者」加星标，修煉程式設計内功
好文章，我在看❤️