欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

寻找有序数组中元素第一次出现的索引和最后一次出现的索引

程序员文章站 2022-03-21 11:38:01
    有序数组 比如 [1,2,3,4,4,4]    这个在js里面可以直接使用findIndex与lastIndexOf来求出,如果我们自己用代码实现该如何做呢?    看到有序数组的查找,没错,二分 二分,对于有序的数据,总能用二分去解决。findIndex的实现代码:var findFirstIndex = (arr, target) => { let l = 0 let r = arr.length - 1 while(l <= r) { let mid = Ma...

    有序数组 比如 [1,2,3,4,4,4]
    这个在js里面可以直接使用findIndexlastIndexOf来求出,如果我们自己用代码实现该如何做呢?

    看到有序数组的查找,没错,二分 二分,对于有序的数据,总能用二分去解决。

findFirstIndex的实现代码:

var findFirstIndex = (arr, target) => {
 let l = 0
 let r = arr.length - 1
 while(l <= r) {
   let mid = Math.floor( (l + r) / 2 )
   let val = arr[mid]
   if (val === target  && ( (mid - 1) < 0 || arr[mid - 1] < val)) {
     return mid
   }
   if (val < target) {
     l = mid + 1
   }
   // 等于要加入,不然重复数据会有死循环
   if (val >= target) {
     r = mid - 1
   }
 }
 return -1
}


findLastIndex同理

本文地址:https://blog.csdn.net/a5534789/article/details/111084673