【面试:基础篇01:整数二分查找】

简介: 【面试:基础篇01:整数二分查找】

【面试:基础篇01:整数二分查找】

01.简介

二分查找是查找算法的一种,在顺序情况下有着 $\log_2^N$良好的时间复杂度

02.算法步骤

在{1,3,5,6,7,9,13,25,34,61,88} 总共11个元素中 找到25的步骤,规定下标从0开始

  1. 首先我们选择下标0,10作为左右边界l,r 中间值mid=(l+r)/2,注意:这里的l+r均为整数 除2的结果若为小数向下取整
  2. 此时我们的mid=5,即元素9不等于25,然后我们令l=mid+1,注意:这里是mid+1而不是mid因为我们已经确定mid这个下标所对应的元素不等于25 所以我们之间从mid+1开始找就行
  3. 此时我们的l=6 r=10,mid=(l+r)/2=8 即元素34,此时34大于25,我们令r=mid-1
  4. 此时我们的l=6 r=7,mid=(l+r)/2=6 即元素13 令l=mid+1
  5. 此时我们的l=7 r=7,mid=(l+r)/2=7 即元素25 找到了元素25 此时返回对应下标7

可以看出我们总共查找了四次就查出了结果

03.算法实现

public static void main(String[] args) {
        int[] a = {1,3,5,6,7,9,13,25,34,61,88};// 排序好的数组
        int res= 25;//要查找的数
        int result = Search(a,res);
        System.out.println(result);
    }

    private static int Search(int[] a,int res) {
        int l=0,r=a.length-1;
        while (l<=r){
            System.out.println("l:"+l+" r:"+r);
            int mid = (l+r)/2;
            if (a[mid]<res){
                l=mid+1;
            }else if (a[mid]>res){
                r=mid-1;
            }else{
                return mid;
            }
        }
        return -1;
    }

结果

l:0 r:10
l:6 r:10
l:6 r:7
l:7 r:7
7
可以看出和我们的推理一样 查询了四次 最终的结果下标为7

04.优化mid溢出问题

问题介绍:

当我们mid=(l+r)/2时 l+r如果数值过于大就会溢出

例子

public static void Overflow(){// 整数溢出问题
        int l=0,r=Integer.MAX_VALUE-1;
        int mid = (l+r)/2;
        System.out.println(mid);
        l=mid+1;
        mid = (l+r)/2;
        System.out.println(mid);// mid太大溢出
    }

结果

-536870913,可以看出此时mid已经溢出

解决方法1

public static void Overflow1(){// 整数溢出问题
    int l=0,r=Integer.MAX_VALUE-1;
    int mid = (l+r)/2;
    l=mid+1;
    mid = (l+r)/2;
    System.out.println(mid);// mid太大溢出
    //此时我们变化形式
    mid = l+(r-l)/2;
    System.out.println(mid);// 可以看出此时没有溢出
}

结果

-536870913 // 溢出时的结果
1610612735 // 变换形式后的结果

可以看出此时阻止了溢出

解决方法2

private static void Overflow2() {
    int l=0,r=Integer.MAX_VALUE-1;
    int mid = (l+r)>>>1;
    System.out.println(mid);
    l=mid+1;
    mid = (l+r)>>>1;// 采用位运算 右移一位避免溢出
    System.out.println(mid);
}

结果

1073741823
1610612735

可以看出此时也没有溢出

方法2 采用的是位运算中的右移运算1,是最推荐的写法,速度快,结果准

05.面试题

  1. 有一个有序表1,5,8,11,19,22,31,35,40,45,48,49,50 当二分查找48时 查找成功需要比较的次数是?
  2. 使用二分查找在序列 1,4,6,7,15,33,39,50,64,75,78,81,89,96 当二分查找81时 需要经过几次比较?
  3. 在拥有128个元素的数组中二分查找一个数,需要比较的次数最多不超过多少次
第一题:

可以看出这和我最开始举得例子基本一致

第一次 我们的l=0 r=12,所以mid=(l+r)/2=6 ,此时mid下标对应的元素是31小于48 所以我们令l=mid+1

第二次 我们的l=7 r=12,所以mid=(l+r)/2=9,此时mid下标对应的元素是45小于48 所以我们令l=mid+1

第三次我们的l=10 r=12,所以mid=(l+r)/2=11,此时mid下标对应的元素是49大于48 所以我们令r=mid-1

第四次我们的l=10 r=10,所以mid=(l+r)/2=10,此时mid下标对应的元素是48 即我们需要的元素

自此我们找到元素48共经过四次比较

第二题与第一题基本一样 所以不在赘述

第三题:

因为二分查找的时间复杂度是$log_2^N$ ,所以此题的答案就是$log_2 128$ 等于7

注意:如果 $log_2^N$ 的结果不是整数 则向下取整+1


  1. 右移运算是指二进制形式下整体向右移一位,溢出的那一位向右移入高位,最低位向右移除,完成除二操作,但注意:右移1位并不是完全等价于除2,当为正数时等价,为负数时不等价
目录
相关文章
|
7月前
|
算法 C++
【面试必刷TOP101】二分查找-I & 二维数组中的查找
【面试必刷TOP101】二分查找-I & 二维数组中的查找
30 0
|
7天前
|
算法
【一刷《剑指Offer》】面试题 11:数值的整数次方
【一刷《剑指Offer》】面试题 11:数值的整数次方
|
9天前
|
Python
2024年最新【Python】常见的 数据类型:整数类型,Python面试题整理最新
2024年最新【Python】常见的 数据类型:整数类型,Python面试题整理最新
2024年最新【Python】常见的 数据类型:整数类型,Python面试题整理最新
|
14天前
|
算法 Java
【力扣经典面试题】12. 整数转罗马数字
【力扣经典面试题】12. 整数转罗马数字
|
14天前
|
机器学习/深度学习 算法 搜索推荐
|
14天前
|
存储 算法 Java
数据结构和算法面试题:给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
数据结构和算法面试题:给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
45 0
|
14天前
|
机器学习/深度学习 存储 算法
数据结构与算法面试题:给定非负整数 m 和 n,计算不大于 m 的数字中,素数的个数。(提示:算法原理为埃氏筛、线性筛)
数据结构与算法面试题:给定非负整数 m 和 n,计算不大于 m 的数字中,素数的个数。(提示:算法原理为埃氏筛、线性筛)
42 0
|
14天前
|
人工智能 算法 Java
数据结构与算法面试题:给定 n 个非负整数 a1,a2,a3,...,an,每个数代表坐标中的一个点(i, ai),请找出两个点之间的最大距离。(提示:动态规划)
数据结构与算法面试题:给定 n 个非负整数 a1,a2,a3,...,an,每个数代表坐标中的一个点(i, ai),请找出两个点之间的最大距离。(提示:动态规划)
54 1
|
14天前
面试题 05.06:整数转换
面试题 05.06:整数转换
18 0
|
9月前
|
存储 Java
LeetCode150道面试经典题--罗马数字转整数(简单)
罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。其按规律组合成一个罗马数字后将其转换成整数并输出。
46 0