题目

image.png
image.png

题解

这道题的关键是如何使用二分算法将符条件的最左面的值和最右面的值找到，不可以投机取巧，因为你不知道你要找的值会在数组中重复多少次出现
如何找最左面符合条件的值。
平常我使用二分算法都是找中间值，但是却没想到 >= 和<=情况下指针的指向，当找到一个符合条件的值后它的附近说不定还有重复值，利用大于等于和小于大于让指针继续往下走，这时候你就的想想指针怎吗停止判断，实在想不出来就画图。找到最右面的值也是这个思路

代码

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number[]}
  5.  * 一个升序的数组
  6.  * [1,2,3,3,3,3,4,5,9]
  7.  * [3,3,3]
  8.  * [1,4]
  9.  * [1]
  10.  * 找到最左边符合条件的数字
  11.  * l <= r 时 进行循环
  12.  * m >= target  r = m - 1
  13.  * m < target  l = m +1
  14.  * 结束时左指针指向最左边的符合条件的数字
  15.  * 找到最右边符合条件的数字
  16.  * l <= r
  17.  * m > target r = m - 1
  18.  * l <= target l = m + 1
  19.  */
  20. var searchRange = function(nums, target) {
  21.     if(nums.length < 1) return [-1,-1];
  22.     const l = searchLeftRange(nums, target);
  23.     const r = searchRightRange(nums, target);
  24.     const len = nums.length;
  25.     if(l > -1 && r > -1) {
  26.         return [l ,r]
  27.     }else if (l > -1){
  28.         return [l, l]
  29.     }else if (r > -1) {
  30.         return [r, r]
  31.     }else {
  32.         return [-1, -1]
  33.     }
  35. };
  36. function searchLeftRange (nums, target) {
  37.     let l = 0;
  38.     let r = nums.length - 1;
  39.     let mid  = 0;
  40.     while(l <= r) {
  41.         mid = (l + r) >> 1 
  42.         if(nums[mid] >= target) r = mid -1 
  43.         else l = mid + 1
  44.     }
  45.     return nums[l] == target ? l : -1;
  46. }
  47. function searchRightRange(nums, target) {
  48.     let l = 0;
  49.     let r = nums.length - 1;
  50.     let mid  = 0; 
  51.     while(l <= r) {
  52.         mid = (l + r) >> 1
  53.         if(nums[mid] > target) r = mid - 1
  54.         else l = mid + 1
  55.     }
  56.     return nums[r] == target ? r : -1;
  57. }

优化后

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number[]}
  5.  * 一个升序的数组
  6.  * [1,2,3,3,3,3,4,5,9]
  7.  * [3,3,3]
  8.  * [1,4]
  9.  * [1]
  10.  * 找到最左边符合条件的数字
  11.  * l < r 时 进行循环
  12.  * m >= target  r = m - 1
  13.  * m < target  l = m +1
  14.  * 结束时左指针指向最左边的符合条件的数字
  15.  * 找到最右边符合条件的数字
  16.  * l <= r
  17.  * m > target r = m - 1
  18.  * l <= target l = m + 1
  19.  */
  20. var searchRange = function(nums, target) {
  21.     if(nums.length < 1) return [-1,-1];
  22.     const l = searchLeftRange(nums, target);
  23.     const r = searchRightRange(nums, target);
  24.     return [l, r]
  26. };
  27. function searchLeftRange (nums, target) {
  28.     let l = 0;
  29.     let r = nums.length - 1;
  30.     let mid  = 0;
  31.     while(l <= r) {
  32.         mid = (l + r) >> 1 
  33.         if(nums[mid] >= target) r = mid -1 
  34.         else l = mid + 1
  35.     }
  36.     return nums[l] == target ? l : -1;
  37. }
  38. function searchRightRange(nums, target) {
  39.     let l = 0;
  40.     let r = nums.length - 1;
  41.     let mid  = 0; 
  42.     while(l <= r) {
  43.         mid = (l + r) >> 1
  44.         if(nums[mid] > target) r = mid - 1
  45.         else l = mid + 1
  46.     }
  47.     return nums[r] == target ? r : -1;
  48. }

将searchLeftRange函数与searchRightRange函数整合到searchRange函数表达式中

  1. /**
  2.  * @param {number[]} nums
  3.  * @param {number} target
  4.  * @return {number[]}
  5.  * 一个升序的数组
  6.  * [1,2,3,3,3,3,4,5,9]
  7.  * [3,3,3]
  8.  * [1,4]
  9.  * [1]
  10.  * 找到最左边符合条件的数字
  11.  * l < r 时 进行循环
  12.  * m >= target  r = m - 1
  13.  * m < target  l = m +1
  14.  * 结束时左指针指向最左边的符合条件的数字
  15.  * 找到最右边符合条件的数字
  16.  * l <= r
  17.  * m > target r = m - 1
  18.  * l <= target l = m + 1
  19.  */
  20. var searchRange = function(nums, target) {
  21.     if(nums.length < 1) return [-1,-1];
  22.     const leftRange = () => {
  23.         let l = 0;
  24.         let r = nums.length - 1;
  25.         let mid = 0;
  26.         while(l <= r) {
  27.             mid = (l + r) >> 1;
  28.             if(nums[mid] >= target) r = mid -1;
  29.             else l = mid + 1;
  30.         }
  31.         return nums[l] == target ? l : -1;
  32.     };
  33.     const reightRange = () => {
  34.         let l = 0;
  35.         let r = nums.length - 1;
  36.         let mid = 0;
  37.         while(l <= r) {
  38.             mid = mid = (l + r) >> 1;
  39.             if(nums[mid] > target) r = mid -1;
  40.             else l = mid + 1;
  41.         }
  42.         return nums[r] == target ? r : -1;
  43.     };
  44.     return [leftRange(), reightRange()]
  46. };