专栏首页面试经验贴二分查找以及变种的总结

二分查找以及变种的总结

一、初探二分查找

在面试的时候,尤其的一面,感觉让你手写二分,还真的不一定就能很快写出来,所以在此总结分享给大家

1 二分查找是什么?

”查找“顾名思义是在一堆数去找出我们需要的数,但是我们又想更快的找出我们需要找的数,所以我们就尽量的减少查找比较的次数。"二分"就是分成两份来减少我们查找次数。

不急不急,假设我们这里有十个数,我们来画图看看这是个什么神操作。

从上图我们知道,我们每次都和区间的中间项值进行比较,从而缩小查找区间的值。

2 时间复杂度?

这里我们假设搜索区间一共n个数,第一次切分n/2,第二次n/4,第三次n/8……….n/2(k).这是一个等比数列,n/2^k=1,k=log2n,那么时间复杂度为o(logn).

二 、二分的注意事项

1 二分查找要求数据必须是有序的。 2 二分查找依赖于数组随机查找的特性,要求内存连续

三 、二分的实现

1 第一种小白写法

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

面试官发话了

2 方法二优化版 如果right和left比较的时候,两者之和可能溢出。那么改进的方法是mid=left+(right-left)/2.还可以继续优化,我们将除以2这种操作转换为位运算mid=left+((right-left)>>1).

哪有这么简单的事儿,大多数的笔试面试中可能会出现下面的几种情况。

四 、二分的各种变种

这里主要是看看原始数组有重复数的情况。

1 查找第一个值等于给定值的情况(查找元素7) 思路

首先7与中间值a[4]比较,发现小于7,于是在5到9中继续查找,中间a[7]=7,但是这个数7不是第一次出现的。那么我们检查这个值的前面是不是等于7,如果等于7,说明目前这个值不是第一次出现的7,此时更新rihgt=mid-1.ok我们看看代码

int BinarySerach(vector<int>& nums, int n,int target) {
    int left = 0, right = n-1;
    while (left <= right) {
        int mid = left+((right-left)>>1);
        if (nums[mid]>value)
        {
            right=mid-1;
        } else if(nums[mid]<value)
        {
            left=mid+1;
        }else
        {
            if((mid==0)||(nums[mid-1]!=value))
            {
                return mid;
            }else
            {
                left=mid-1;
            }
        }
    return -1;
}

2 查找最后一个值等于给定值的情况

假设nums[mid]这个值已经是最后一个元素了,那么它肯定是要找到最后一个值。如果nums[mid]的下一个不等于value,那说明nums[mid]就是我们需要找到最后一个等于给定值的值。

int BinarySerach(vector<int>& nums, int n,int target) {
    int left = 0, right = n-1;
    while (left <= right) {
        int mid = left+((right-left)>>1);
        if (nums[mid]>value)
        {
            right=mid-1;
        } else if(nums[mid]<value)
        {
            left=mid+1;
        }else
        {
            if((mid==n-1)||(nums[mid+1]!=value))
            {
                return mid;
            }else
            {
                left=mid+1;
            }
        }
    return -1;
}

3 查找第一个大于等于给定值的情况

1 如果nums[mid]小于要查找的值,那么我们需要查找在[mid+1,right]之间,所以此时更新为left=mid+1 2 如果nums[mid]大于给定值value,这个时候需要查看nums[mid]是不是我们需要找的第一个值大于等于给定值元素,如果nums[mid]前面没有元素或者前面一个元素小于查找的值,那么nums[mid]就是我们需要查找的值。相反 3 如果nums[mid-1]也是大于等于查找的值,那么说明查找的元素在[left,mid-1]之间,所以我们需要将right更新为mid-1

int BinarySerach(vector<int>& nums, int n,int target) {
    int left = 0, right = n-1;
    while (left <= right) {
        int mid = left+((right-left)>>1);
        if (nums[mid]>=value)
        {
            if(mid==0||nums[mid-1]<value)
            {
                return mid;
            }else
            {
                right=mid-1;
            }
        }else
        {
            left=mid+1;
        }
    return -1;
}

4 查找最后一个小于等于给定值的情况

1 如果nums[mid]小于查找的值,那么需要查找的值肯定在[mid+1,right]之间,所以我们需要更新left=mid+1 2 如果nums[mid]大于等于给定的value,检查nums[mid]是不是我们的第一个值大于等于给定值的元素

int BinarySerach(vector<int>& nums, int n,int target) {
    int left = 0, right = n-1;
    while (left <= right) {
        int mid = left+((right-left)>>1);
        if (nums[mid]>value)
        {
            right=mid-1;
        }else
        {
            if(mid==n-1||(nums[mid+1]>value))
            {
                return mid;
            }else
            {
                left=mid+1;
            }
        }
    return -1;
}

本文分享自微信公众号 - 我是程序员小贱(Lanj1995Q),作者:lj

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-28

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 「手撕算法」锁定大厂看这就可

    那么数据结构中的结构定义是这个数据结构长什么样子,有些什么性质?结构的操作意思是这个结构可以支持什么操作,但是不管你怎么的操作,不能破坏了它的结构

    我是程序员小贱
  • [leetcode数组系列]2三数之和

    在思考两数之和解决方法的时候,我们使用了两层循环把所有的结果给求出来,相信读者很快就想到三数之和我就用三个循环,很棒,思路是一样,只是之前的a+b=0,现在的b...

    我是程序员小贱
  • [leetcode数组系列]3 删除排序数组中的重复项

    1 leetcode原文链接 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-ar...

    我是程序员小贱
  • 二分查找以及变种的总结

    ”查找“顾名思义是在一堆数去找出我们需要的数,但是我们又想更快的找出我们需要找的数,所以我们就尽量的减少查找比较的次数。"二分"就是分成两份来减少我们查找次数。...

    kunge
  • LeetCode题目35:搜索插入位置

    给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

    二环宇少
  • 用C++写二分查找了!【手绘漫画】图解LeetCode之搜索插入位置(LeetCode 35)

    正常的二分查找,除了两个特殊的条件,即,如果数组中没有 target,小于最小值或者大于最大值,则返回插入的位置。

    我是管小亮
  • [LeetCode] 153. Find Minimum in Rotated Sorted Array

    【原题】 Suppose an array sorted in ascending order is rotated at some pivot unkno...

    用户1148830
  • 【手绘漫画】图解LeetCode之寻找峰值(LeetCode 162题)

    首先分析一下情况,如果 mid 一直比右侧的数小,那么 mid 处的值肯定不是峰值。

    我是管小亮
  • 漫画:知乎面试题(旋转数组最小值Ⅰ - 基础版)

    今天是小浩算法“365刷题计划”第71天。继续为大家讲解二分查找,分享一道知乎面试题。话不多说,直接看题。

    程序员小浩
  • 终于知道两个模板的区别了!【手绘漫画】图解LeetCode之在排序数组中查找元素的第一个和最后一个位置(LeetCode 34)

    最后返回的值写 left 或者 right 都是没问题的!因为 while 的结束条件是 left 和 right 相等。

    我是管小亮

扫码关注云+社区

领取腾讯云代金券