JSアルゴリズム問題の毎日1問題-17.ソート配列で要素の最初の位置と最後の位置を検索
1127 ワード
微信公衆番号:
酔っ払う、より多くのテーマに注目してください.
例1: 入力:nums=[5,7,7,8,8,10],target=8,出力:[3,4]例2: 入力:nums=[5,7,7,8,8,10],target=6,出力:[-1,-1]
酔っ払う、より多くのテーマに注目してください.
タイトル
Q:は、昇順に配列された整数配列numsと、ターゲット値targetとを与える.配列内の所定のターゲット値の開始位置と終了位置を特定します.あなたのアルゴリズムの時間複雑度はO(log n)レベルでなければなりません.配列にターゲット値が存在しない場合は、[-1,-1]を返します.答え
const searchRange = (nums, target) => {
let targetIndex = binarySearch(nums, target, 0, nums.length - 1);
if (targetIndex == -1) return [-1, -1];
let l = targetIndex, r = targetIndex;
while(l > 0 && nums[l - 1] == target) {
l--;
}
while(r < nums.length - 1 && nums[r + 1] == target) {
r++;
}
return [l, r];
};
const binarySearch = (arr, val, lo, hi) => {
if (hi < lo) return -1;
let mid = lo + parseInt((hi - lo) / 2);
if (val < arr[mid]) {
return binarySearch(arr, val, lo, mid - 1);
} else if (val > arr[mid]) {
return binarySearch(arr, val, mid + 1, hi);
} else {
return mid;
}
}