LeetCode-【配列】-ソート配列で要素の最初と最後の位置を検索します.

昇順に配列された整数配列を指定します.  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]

标题:時間の複雑さを見るとO(log) n)レベルであり,配列は昇順に配列されており,二分探索の方法が容易に考えられ,二分探索は配列に関する問題を解決する際に本当に神出鬼没することがある.

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int n=nums.length;
        int[] res=new int[2];
        res[0]=-1;res[1]=-1;
        int l=0,r=n-1,c=0;
        while(l<=r){
            int mid=(l+r)/2;
            if(nums[mid]==target){
                 int i=mid;
                 int j=mid;
                 while(i>=0&&nums[i]==target) 
                     i--;
                 res[0]=i<0?0:i+1;
                 while(jn?n-1:j-1;
                 return res;
            }
            if(nums[mid]target)
                r=mid-1;
        }
        return res;
    }
}