二分查找(旋转数组的最小值)
本文最后更新于 179 天前,其中的信息可能已经有所发展或是发生改变。

二分查找

二分查找是一种应用了分治思想的查找算法,基本思想十分简单,只是对于一些特殊问题有一些小点需要注意,将在后面例题中介绍。

应用范围

顺序存储的数据集中查找某个目标值

顺序存储可以是升序降序,一些特殊情况甚至可以是部分有序(比如即将介绍的旋转数组问题)

基本思想

此处以升序的数据集作为例子,将数据集中间位置的值与目标值进行比较,如果比目标值大则将尾指针移动至中间位置,对于头尾指针之间的数据继续进行二分查找;如果中间位置的值比目标值小则将头指针移动至数据集中间。时间复杂度可以做到$O(n) = log_2n$。

例题:旋转数组问题

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。例如,数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转,该数组的最小值为1。

示例 1:

输入:[3,4,5,1,2]
输出:1

示例 2:

输入:[2,2,2,0,1]
输出:0

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

这个数组即前面提到的“部分有序”,是升序 但又不完全是,由于需要查找的元素所处位置的特殊性而且以查找元素为分界线前后元素均有序,所以可以使用二分查找进行解题。

上代码

class Solution {
    public int minArray(int[] numbers) {
        int i,j,m;
        j = numbers.length-1;
        i = 0;
        m = (i+j)/2;
        while(i!=j){
            if(numbers[m]<numbers[j]){
               j = m;
               m = (i+j)/2;
            }
            else if(numbers[m]>numbers[j]){
                i = m+1;
                m = (i+j)/2;
            }
            else if(numbers[m] == numbers[j]){
                j = j-1;
                m = (i+j)/2;
            }
        }
        return numbers[i];
    }
}

一个小点

这个题解前面大部分就是基本的二分查找,但是:在一些特殊情况下,如本题的

第16行处 遇到重复值的情况如何处理:

  1. 当 x<jx < jx<j 时: 易得执行 j=j−1j = j - 1j=j−1 后,旋转点 xxx 仍在区间 [i,j][i, j][i,j] 内。

  2. 当 x=jx = jx=j 时: 执行 j=j−1j = j - 1j=j−1 后越过(丢失)了旋转点 xxx ,但最终返回的元素值 nums[i]仍等于旋转点值 nums[x] 。

二分”猜“找

前面说二分可以用于顺序存储的数据集中查找目标值;
但是在刷题时发现不仅不一定是顺序存储,甚至不一定要有数据集,只要有个范围有单调性就可以用二分来“猜”结果。比如下面这道题

珂珂喜欢吃香蕉。这里有 n 堆香蕉,第 i 堆中有 piles[i] 根香蕉。警卫已经离开了,将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 k 根。如果这堆香蕉少于 k 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃,但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k(k 为整数)。
示例 1:
输入:piles = [3,6,7,11], h = 8
输出:4
示例 2:
输入:piles = [30,11,23,4,20], h = 5
输出:30
示例 3:
输入:piles = [30,11,23,4,20], h = 6
输出:23
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/koko-eating-bananas
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

明显吃香蕉的速度有上下限(1~piles.maxValue()),而且速度与时间具有单调性,所以可以使用二分猜一个答案出来,时间复杂度甚至很低;

ps:其实我最开初思路是模拟法,但是结果总是不对,暂时还没看出来错在了哪里,记录一下

如果时间与香蕉的堆数相同,那么最慢速度就是最大堆的香蕉数;如果时间是香蕉堆数+1,那么为了降低我的速度,就可以将最大堆分两次吃完,此时的最低速度就是将最大堆除二之后所有堆中最大堆的香蕉数;以此类推就可以得出结果

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇