Day242:实现一个函数 findLastIndex(), 返回指定数在“有序”数组中最后一次出现位置的索引。如 findLastIndex([1,2,3,3,3,4,5], 3), 返回 4。时间复杂度是多少？什么情况下时间复杂度最高？

[Genzhen]

每日一题会在下午四点在交流群集中讨论，五点小程序中更新答案
欢迎大家在下方发表自己的优质见解
二维码加载失败可点击 小程序二维码

扫描下方二维码，收藏关注，及时获取答案以及详细解析，同时可解锁800+道前端面试题。

---

参考代码实现

• 实现方式一

类似这种题目，我们第一时间想到的就是二分查找法，然后对于重复数字的处理再用逼近方法，基本就可以得出答案了。时间复杂度时 O(logn)。

如果用暴力法破解，时间复杂度将是 O(n)。最复杂的情况是数组全部遍历之后才能得出最终结果。

function findLastIndex(arr, target) {
  const len = arr.length;
  let left = 0,
    right = len - 1;

  while (true) {
    if (arr[left] > target || arr[right] < target) return -1;

    let middle = Math.floor((right - left) / 2 + left);
   if (arr[middle] > target) {
      right = middle;
    } else {
      left = middle;
    }
    
    if (left + 1 === right && arr[right] === target) {
      return right;
    }

    if (left + 1 === right && arr[left] === target) {
      return left;
    }
  }
}
console.log(findLastIndex([1, 2, 3, 3, 3, 4, 5], 3));

• 实现方式二

const findLastIndex = (nums, target) => {
  const len = nums.length;
  if (len < 1) return -1;
  let l = 0,
    r = len;
  while (l < r) {
    const mid = (l + r) >> 1;
    target < nums[mid] ? (r = mid) : (l = mid + 1);
  }
  return l - 1;
};
console.log(findLastIndex([1, 2, 3, 3, 3, 4, 5], 3));

二分查找时间复杂度 O(logn)，target 为数组最后一个的时候复杂度最高 还是 O(logn)。

[zhangyuinfinite]

二分法里有一行写错了，应该是

if (arr[middle] === target) {
  left = middle;
} else if (arr[middle] > target) {
  right = middle;
} else {
  left = middle;
}

[liuhui219]

function findLastIndex(arr,n){
let result;
for(let i=0;i<arr.length;i++){
if(arr[i] === n && arr.indexOf(arr[i],i+1) === -1){
result = i
}
}

return result
}

[luuman]

通过有序数组，查找，想到二分查找法。

方法：

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

二分查找

var arr = [1, 3, 5, 7, 9, 10, 11, 12, 14, 15, 19, 20]
function findLastIndex(nums, target) {
 let left = 0, right = nums.length - 1
  while (left <= right) {
      let mid = parseInt((left + right) / 2)
      if (target < nums[mid]) {
          right = mid - 1
      } else if (target > nums[mid]) {
          left = mid + 1
      } else {
          return mid
      }
  }
  return -1
}
console.log(findLastIndex(arr, 4))

var arr = [1, 3, 5, 7, 9, 10, 11, 12, 14, 15, 19, 20]
function findLastIndex(nums, target) {
  let result = -1
  nums.forEach((element, index) => {
      if (element === target){
          result = index
      }
  })
  return result
}
console.log(findLastIndex(arr, 4))

（版本一）左闭右闭区间

var search = function(nums, target) {
  let l = 0, r = nums.length - 1
  // 区间 [l, r]
  while(l <= r) {
    let mid = (l + r) >> 1
    if(nums[mid] === target) return mid
    let isSmall = nums[mid] < target
    l = isSmall ? mid + 1 : l
    r = isSmall ? r : mid - 1
  }
  return -1
}

（版本二）左闭右开区间

var search = function(nums, target) {
  let l = 0, r = nums.length
  // 区间 [l, r）
  while(l < r) {
    let mid = (l + r) >> 1
    if(nums[mid] === target) return mid
    let isSmall = nums[mid] < target
    l = isSmall ? mid + 1 : l
    // 所以 mid 不会被取到
    r = isSmall ? r : mid
  }
  return -1
}

[luuman]

[luuman]

暴力法破解

O(n)

function findLastIndex(arr, target) {
  const len = arr.length
  let left = 0,
    right = len - 1
  while (true) {
    if (arr[left] > target || arr[right] < target) return -1
    let middle = Math.floor((right - left) / 2 + left)
  	console.log(arr[left], target, middle, (right - left))
	  if (arr[middle] > target) {
      right = middle
    } else {
      left = middle
    }
    console.log(left + 1 === right, arr[right] === target, arr[left] === target)
    if (left + 1 === right && arr[right] === target) {
      return right
    }
    if (left + 1 === right && arr[left] === target) {
      return left
    }
  }
}
console.log(findLastIndex([-1,0,3,5,9,12], 1))
报错 查询不到