Open Genzhen opened 3 years ago
二分法里有一行写错了,应该是
if (arr[middle] === target) { left = middle; } else if (arr[middle] > target) { right = middle; } else { left = middle; }
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 }
通过有序数组,查找,想到二分查找法。
搜索过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜索过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空,则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
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
}
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))
报错 查询不到
扫描下方二维码,收藏关注,及时获取答案以及详细解析,同时可解锁800+道前端面试题。
参考代码实现
类似这种题目,我们第一时间想到的就是二分查找法,然后对于重复数字的处理再用逼近方法,基本就可以得出答案了。时间复杂度时 O(logn)。
如果用暴力法破解,时间复杂度将是 O(n)。最复杂的情况是数组全部遍历之后才能得出最终结果。
二分查找时间复杂度 O(logn),target 为数组最后一个的时候复杂度最高 还是 O(logn)。