算法——二分查找_业界新闻

发布时间:2024-07-17 17:36

阅读量:0

前言：本篇文章继续分享一种新的算法——二分查找。

一.二分查找

给定一个 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

按照一般的方法去解决上述题目，我们的第一想法肯定是将数组从头到尾遍历一遍，每个值都跟target进行一次比较，从而判断其是否存在于数组中。

此方法虽然简单，但是在最差的情况下，需要进行n次循环，即时间复杂度为O(N)，如果说在数据量很大的前提下，这样做的速度反而是非常慢的。

但是有了数组已经有序（升序）的前提，所以为了降低时间复杂度，引出二分查找的概念：

取一组数据的中间值与target进行比较，如果相等，就直接返回；
如果中间值比target小，那么数组中的目标值就一定在中间值的右边；
如果中间值比target大，那么数组中的目标值就一定在中间值的左边；

通过中间值的方法，不断将数组拆分成两半，便可以使其中一半不满足条件的数据直接舍弃，无需在进行判断，如此以来的时间复杂度变为O(logN)。

下面来看具体代码：

    int search(vector<int>& nums, int target) {         int left = 0,right = nums.size() - 1;         while(left <= right)         {             int midnum = left + (right - left) / 2;             if(nums[midnum] == target)             {                 return midnum;             }             else if(nums[midnum] > target)                 right = midnum - 1;             else                 left = midnum + 1;         }         return -1;     }

二分查找，需要定义两个指针left和right，分别管理要处理的数据的两端，起始时为整个数组的两端。

随后我们需要得出中间值，求中间值有一个细节，如果我们使用(right + left) / 2的方式去求算中间值，那么当left和right均接近于INT_MAX时，就会发生数据越界，所以我们采用上述代码的方式更加稳妥。

随后进行比较，当中间值和target相等时，遍返回中间值下标；如果中间值比target大，则说明目标值在中间值的左边，此时更新right，反之则更新left，取半查找。

直到找到数据，或者left > right，即数组中不存在target时，循环方可结束。

值得注意的是，二分查找并不局限于有序的数组，凡是能够通过某种规律将数据不断分成两半的，均可使用二分查找算法。

二.x的平方根

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。
正数的平方根有两个，只输出其中的正数平方根。
如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。
示例 1:
输入: x = 4 输出: 2 
示例 2:
输入: x = 8 输出: 2 解释: 8 的平方根是 2.82842...，由于小数部分将被舍去，所以返回 2

本题也是一道相对简单的题，因为我们无法使用平方根函数直接解题，所以想要得到一个数的平方根，我们必须从1开始，算每个数的平方，直至算到x的平方，判断是否有一个数的平方为x。

这其实和从一个升序数组中找一个值是一样的，所以本题为了降低时间复杂度，我们需要采用二分查找的算法：1~x的中点值的平方是否为x作为判断二分条件，随后比较大小进行二分。

    int mySqrt(int x) {         if(x == 0)             return 0;         int left = 1, right = x;         while(left < right)         {             long long mid = left + (right - left + 1) / 2;             long long sum = mid * mid;             if(sum > x)                 right = mid - 1;             else                 left = mid;         }         return left;     }

但是本题有一个特殊情况，因为一个非负整数的平方根不一定也是一个整数，所以我们要取其取余后的整数部分，也就是说实际要求的整数比其平方根要小。

所以在进行区间截取时，我们需要进行改动， 因为结果小于等于目标值都有可能，所以我们需要将<=的情况放在一起判断。并且当left变动时，不能再取mid+1，因为有可能mid正好就是那个取余后的整数。

同样，我们求中间节点的方法也需要进行优化：

实际上除了第一个题目中：left + (right - left) / 2这个求中的的方法外，还有一种方法：

left + (right - left + 1) / 2

那么多的这个＋1，会有什么影响呢？？？

首先，当从left到right有奇数个数据时，使用这两种方法，所求mid均为中间值。

但是当从left到right有偶数个数据时，前者所求数据为中间值的左边，而后者则为中间值的右边。

这又会产生什么影响？？?

当我们要判断的数据只剩两个时，如果采用 left + (right - left) / 2的方式求中点，当遇到判断结果要让left = mid时，left就会一直等于mid，永远不可能大于等于right，这样就会造成死循环。

同理，如果采用 left + (right - left + 1) / 2的方式求中点，当遇到判断结果要让right = mid时，同样会造成死循环。

所以当出现该情况时，我们只需将上述两种求中点的方法进行交换即可避免死循环。

三.山峰数组的峰值索引

符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i]
arr[i] > arr[i+1] > ... > arr[arr.length - 1]
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < ... arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[arr.length - 1] 的下标 i ，即山峰顶部。
示例 1：
输入：arr = [0,1,0] 输出：1 
示例 2：
输入：arr = [1,3,5,4,2] 输出：2

题目还是很容易理解的，就是在数组中找到最大的一个数，并返回其下标，该数字大于其左边的数单调递增，右边的数单调递减。

我们可以通过直接遍历数组的方法去找这个数，当某数字比它的后一个数大时，即为答案。但是如果该数字为最后一个数，那我们就需要遍历整个数组，时间复杂度为O(N)。

所以为了优化时间复杂度，虽然这道题不是一个有序的数组，但我们依然可以采用二分查找。

在该数组中，某个数不是比它的前一个数大，就是比它的前一个数小，所以我们可以依此为判断条件：

    int peakIndexInMountainArray(vector<int>& arr) {         int left = 0,right = arr.size() - 1;         while(left < right)         {             int mid = left + (right - left + 1) / 2;             if(arr[mid] < arr[mid - 1])                 right = mid - 1;             else                 left = mid;         }         return left;     }

如果mid < mid - 1，说明mid在山的右侧，此时山峰在左半区，所以right左移；当mid >= mid - 1时，此时mid在山的左半边，山峰则在右半区，left右移，但是因为山峰是最大的数字，所以此时mid也可能是山峰，所以left的移动不能超过mid。

mid的计算方法则需按照在第二题中分享的方法进行考虑。