乐趣区

关于leetcode:力扣之二分查找

题目形容

给定一个 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) {......} 看看打印后果就会更好的了解了。尽管会死循环

退出移动版