当前位置: 首页 > Web前端 > JavaScript

前端工程师leetcode算法面试必备-二分查找算法(中)_1

时间:2023-03-27 13:16:03 JavaScript

1.前言二分查找算法本身并不是特别复杂,核心点主要集中在:有序数组:指的是递增或递减的区间(特殊情况如:【852.山脉阵的巅峰指数】);中间数:用于判断搜索目标是落在左半区间还是右半区间;进入中等难度后,这两个条件一般不会直接给出,需要解题者根据题型自行构造。2.LeetCode实战1、378.有序矩阵中第K小的元素水平和垂直方向为数组递增的条件,当前二维空间中左上角为最小值,下方右角是最大值,所以有一个序数数组是一个从最小值到最大值递增的整数序列。题目要求计算第k小的元素,所以从有序数组中选出的中间数不能直接与k进行比较。需要在二维空间中找出当前中间数的最小数,然后与k比较:如果当前中间数大于第k小的元素,那么第k小的元素一定在左半区间;否则,它一定落在右半区间;通过当前二维数组在水平和垂直方向单调递增的特性,可以从左下角开始搜索当前中间数的最小数。也有类似的解题思路:[74.搜索二维矩阵]2,875.爱吃香蕉的珂珂这道题要求我们找到吃香蕉的最慢速度,这样我们可以在H小时内吃到N堆香蕉。珂珂吃香蕉的最慢速度是每小时1个香蕉,最快速度是每小时吃max(N)根。有序数组是从1到max(N)的递增整数序列。从有序数组中找到一个速度后,还需要计算以当前速度吃完所有香蕉所需的时间,并与H比较:如果以当前速度吃完所有香蕉的时间大于H,则要求的搜索速度K必须落在区间的右半部分;反之,K落在区间的左半部分;3、658.找到K个最接近的元素这道题要求我们找到一个起始下标索引,使得[index,index+k)中最接近x的数。本题没有隐藏有序数组的条件,所以本题难点在于如何通过中间下标判断索引落在哪个区间:首先考虑数组边界的问题,如果mid+k>arr。length-1,则索引必须落在区间的左半部分;接下来,利用离x最近的两个条件,优先选择最小的元素(即优先选择左边的元素):如果x左边的差值小于x右边的差值,那么索引必须落在区间的左半部分;还有其他题目类似的解题思路:[275.H索引II]4,34.查找元素在排序数组中的第一个和最后一个位置这个题目比较简单,但是和上一个题目的区别在于查找目标不一定存在于有序数组中,所以搜索结束后,需要注意特殊情况的处理。通过两次二分查找找到目标值的上下限下标,然后将上下限值与目标值进行比较,得到正确的开始下标和结束下标:参考视频:传送门写在最后算法作为计算机的基础学科,刷着JavaScript,一点都不丢脸ε=ε=ε=┏(゜ロツ;)┛。本系列文章将总结算法的三种难度(简单难度、中等难度和困难难度)。简单难度会介绍算法的基础知识和实现,另外两个难度会重点讲解解题思路。如果本文对您有帮助,可以点赞或关注,鼓励博主。