乐趣区

关于leetcode:力扣之二分查找

jiezi

题目形容

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target，写一个函数搜寻 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输出: nums = [-1,0,3,5,9,12], target = 9
输入: 4
解释: 9 呈现在 nums 中并且下标为 4

示例 2:

输出: nums = [-1,0,3,5,9,12], target = 2
输入: -1
解释: 2 不存在 nums 中因而返回 -1

力扣原题目地址：https://leetcode.cn/problems/…

解法一，应用数组原生办法 indexOf

var search = function (nums, target) {return nums.indexOf(target)
};

数组的原生办法，应用真不便。不过有时候须要多拓展一些解决问题的形式，当前遇到需要时，大有裨益

解法二，循环所有判断是否等于目标值

var search = function (nums, target) {
    let whichIndex = -1
    for (let i = 0; i < nums.length; i++) {if (nums[i] == target) {
            whichIndex = i
            return whichIndex
        }
    }
    return whichIndex
};

假如咱们要找的值，就是正好在最初一个地位，那么就得把整个循环全副走一遍，能力找到咱们所要找的那个数值。所以工夫复杂度就是O(n)。为了进一步晋升效率，缩小用时，所以二分法解题的形式就应运而生

解法三，二分法解题

所谓二分法能够简略了解为：

  • 指定开始地位、完结地位、而后一直放大其范畴最终找到咱们想要找到的值；
  • 因为二分法的一半一半的放大范畴，所以其工夫复杂度是O(\log n)

另外留神：

  • 二分法实用于有序的数组，即从小到大或者从大到小的数组
  • 二分法搭配 while 循环可读性会更加直观明了

在工作中 for 循环应用次数比拟多，while 循环并不是特地多，所以为了更好的了解二分法的，咱们来简略温习一下 while 的循环常识

while 循环温习

// 当合乎 condition 条件的时候，会持续一直循环执行花括号外面的代码
// 所以当达到某种状况下的时候，须要让 condition 条件变为 false，这样的话，才会完结循环
// 要不然就会死循环哦
while (condition) {// .....}

// eg: 应用 while 循环打印 0~10
let num = 0
while (num <= 10) { // 翻译：当 num 的值小于等于 10 的时候，就一直循环
    console.log(num);
    num++
}

while 和 for 循环的区别

  • 固定数组、固定长度、固定执行次数个别应用 for 循环
  • 做边界辨别、不晓得要循环多少次个别应用 while 循环
  • while 比 for 性能更加弱小

二分法代码

var search = function (arr, num) {
    let firstIndex = 0
    let lastIndex = arr.length - 1
    // 留神 firstIndex 是要小于等于 lastIndex 值的，因为区间一直放大最终重合
    while (firstIndex <= lastIndex) {// console.log('firstIndex', firstIndex, 'lastIndex', lastIndex); // 看打印后果，有助于更好了解
        let middleIndex = Math.floor((firstIndex + lastIndex) / 2) // 数组长度为偶数时要向下取整，所以罗唆都向下取整呗
        if (arr[middleIndex] == num) { // 若恰好两头索引数正好是咱们所要找的那个数，返回索引即可
            return middleIndex
        } else if (arr[middleIndex] > num) { // 若两头数比要找的数大，阐明要找到数在右边，那么开始区间不必动，完结区间更改为两头数右边一个地位即可
            lastIndex = middleIndex - 1
        } else if (arr[middleIndex] < num) { // 同理...
            firstIndex = middleIndex + 1
        }
    }
    return -1 // 找不到的话，返回 -1
};

这里大家能够把 while (firstIndex <= lastIndex) {......} 改为 while (true) {......} 看看打印后果就会更好的了解了。尽管会死循环

退出移动版