[leetcode] 34. Find First and Last Position of Element in Sorted Array

Given an array of integers 

nums

 sorted in ascending order, find the starting and ending position of a given 

target

 value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return 

[-1, -1]

.

Example 1:

Input: nums = [         5,7,7,8,8,10]                , target = 8
Output: [3,4]      

Example 2:

Input: nums = [         5,7,7,8,8,10]                , target = 6
Output: [-1,-1]      

這個題目嘛，大部分人肯定和我一樣，第一反應絕對是暴力

确實暴力的話這題秒解，時間複雜度也隻會是O(n)而已

然而題目要求了O(log n)那肯定要其他做法

很明顯O(log n)的話隻有二分查找了

一開始我想用遞歸做的，因為快排也是遞歸的嘛，後面想了想最後結果是傳回2個值，遞歸的話好像不好搞啊

于是還是循環去搞了

我犯了一個錯誤，導緻我遲遲沒解出來

首先肯定知道要分3類，我就分了三類，小于target、大于target和剛好等于target的情況

我錯就錯在等于target的時候，處理不對，我一開始是以為剛好等于target的時候，隻有這個數和相鄰的一個數的坐标能傳回

後面錯了N次後才發現不對

于是就針對剛好等于target一定要有一個解決方法

前面錯得太多次了，經過反思，就是我題目意思了解錯了

如果是找間隔最遠的2個坐标，那向兩端找就行了啊！

想通了之後，于是我就很快解出來了

具體方法如下

首先定義一個middle = (left + right) / 2

這個不解釋了

從中間開始，如果nums[middle] > target，那麼很明顯target在middle的左邊，是以這時候right = middle - 1;

如果nums[middle] < target，那麼left = middle + 1;

最重要的就是如果nums[middle] == target

那麼，我們就把left、right都放到middle，也就是left = middle,right = middle;

然後就是從中間往兩邊搜尋了

保證數組不要越界即可

總結來說本題就是先用二分查找法從中間去分治，壓縮搜尋空間

找到結果後又重新從中間往兩邊搜尋，傳回結果

java代碼如下：

public int[] searchRange(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        
        int []answer = new int[]{-1,-1};
        
        if(nums.length == 0)
            return answer;
        
        if(nums[0] > target || nums[nums.length - 1] < target)
            return answer;
        
        while(left <= right){
            int middle = (left + right) / 2;
            if(nums[middle] < target){
                left = middle + 1;
            }
            
            if(nums[middle] > target){
                right = middle - 1;
            }
            
            //找到了之後,從中間向兩邊找到坐标
            if(nums[middle] == target){
                left = middle;
                right = middle;
                
                while(left != 0 && nums[left - 1] == target){
                    left--;
                }
                
                while(right != nums.length - 1 && nums[right + 1] == target){
                    right++;
                }
                
                answer[0] = left;
                answer[1] = right;
                break;
            }
        }
        return answer;
    }
           

我也沒想到用時會這麼短

不過貌似記憶體耗得很大？