寻找有序数组中元素第一次出现的索引和最后一次出现的索引
程序员文章站
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里面可以直接使用findIndex
与lastIndexOf
来求出,如果我们自己用代码实现该如何做呢?
看到有序数组的查找,没错,二分 二分,对于有序的数据,总能用二分去解决。
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