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

問題の説明

減少しない整数配列numsがある場合は、target値の開始位置と終了位置を検索します.
target値が見つからない場合は[1,1]を返します.
必ずO(logn)の時間複雑度で記入してください.

出力例

方法

初めての試み

時間の複雑さの制約を見て、二分探索で近づいた.
まず、新しいbinary search関数を作成し、while文の内部で二分検索を実行すると、より効果的ではないでしょうか.

ソースコード

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int result=-1;
        int start=0;
        int end=nums.size()-1;
        while(start <= end){
            int mid = (start + end)/2;
            if(nums[mid]> target){
                end = mid-1;
            }
            else if(nums[mid] < target){
                start = mid+1;
            }
            else {
               result = mid;
               break;
            }
        }

        int first,second;

        if(result<0) return {-1,-1};
        else {
            for(int i=result; i>=0; i--) {
                if(nums[i]!=target) break;
                else first = i;
            }
            
            for(int j=result; j<nums.size(); j++) {
                if(nums[j]!=target) break;
                else second = j;
            }

            return {first,second};
        }
    }
};

レビュー