二分查找

题目:例如这样一个[1,3,4,5,7]有序的数组,如何快速找到某个值的下标?
这是一个经典的二分查找算法题。

解题思路:

  1. 先找到数组的中间下标值
  2. 然后判断目标值如果大于中间值,就在数组的右半边继续查找
  3. 如果目标值小于中间值,就在数组的左半边继续查找
  4. 然后不断的重复上面的步骤。

时间复杂度是O(logN) 因为遍历减半了就是n的一半=logN,如果遍历了全部就是N

let binarySeach = function (arr, target) {
    let s = 0 // 开始下标
    let e = arr.length - 1 //结束下标
    while (s <= e) { // 如果开始下标小于等于结束下标就标识区间内有值
        let mid = Math.floor((s + e) / 2) //当前数组的中间值下标
        let item = arr[mid] // 中间值
        if (item < target) { //如果中间的值小于目标值
            s = mid + 1 // 把开始下标移动到中间值的后面,在2叉树的右边继续搜索了
        } else if (item > target) { //如果中间值大于目标值
            e = mid - 1 // 把结束下标移动到中间值的前面一位,在2叉树的左边数组继续搜索
        } else { // 如果中间值等于目标值直接返回当前下标
            return mid
        }
    }
    return -1 // 找不到就返回-1
}
let res = binarySeach([1, 2, 3, 4, 5], 2)
console.log(res)
本站文章如未注明均为原创 | 文章作者:刘晓帆 | 转载请注明来自:前端印象

发表评论

邮箱地址不会被公开。 必填项已用*标注

浏览量:116 次浏览