给定一个长度为n的非降序排列的整数数组,和一个目标值 。请找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 ,返回 [-1, -1]
该题有的解法
[4,7,7,8,8,10],8
[3,4]
可以在数组中找到整数8,其开始位置为3,结束位置为4
[4,7,7,8,8,10],6
[-1,-1]
不可以在数组中找到整数6,故输出整数-1
/** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型一维数组 * @param target int整型 * @return int整型一维数组 */ function searchRange( nums , target ) { // 用二分法寻找左右侧的边界 let left = findLeftBorder(nums , target); let right = findRightBorder(nums , target); return [left, right]; // 获取左侧边界的函数 function findLeftBorder(nums , target) { let left = 0, right = nums.length - 1; while(left <= right) { let mid = Math.floor(left + (right - left)/2); if(nums[mid] < target) { left = mid + 1; } else if(nums[mid] > target) { right = mid - 1; } else if(nums[mid] === target) { right = mid - 1; } } if(left >= nums.length || nums[left] !== target) { return -1; } else { return left } } // 获取右侧边界的函数 function findRightBorder(nums , target) { let left = 0, right = nums.length - 1; while(left <= right) { let mid = Math.floor(left + (right - left)/2); if(nums[mid] < target) { left = mid + 1; } else if(nums[mid] > target) { right = mid - 1; } else if(nums[mid] === target) { left = mid + 1; } } if(right < 0 || nums[right] !== target) { return -1; } else { return right; } } } module.exports = { searchRange : searchRange };