【牛客算法-二分查找】刷题和面试兼顾还得看你啊

简介: 【牛客算法-二分查找】刷题和面试兼顾还得看你啊

1.二分查找-1

点我做题:二分查找-1

dea6ae8902d64804a37004c5406d7d1e.png

题目描述:在一个数组中找某个目标值,找到返回下标,找不到返回-1(题目简单)

int search(int* nums, int numsLen, int target ) {
    int left=0;
    int right=numsLen-1;
    while(left<=right)
    {
        int  mid=(left+right)/2;
        if(nums[mid]>target)
        {
            right=mid-1;
        }
        else if(nums[mid]<target)
        {
            left=mid+1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}

267d889edab14ae8b25013f9899cae23.png

我思考的两个问题:


while(left<=right)终止条件是left>right,在left==right相遇点的值可能是target

a[mid]>或<target时则说明a[mid]不是目标值,则要将下标为mid的值排除在新的区间外

变式1:

题目给定无重复元素,但如果题目考虑数组中的目标值存在且可以重复且要你返回第一个目标值,那你该怎么做?


2.二维数组中的查找

点我做题:二维数组中的查找

e4070ab153a049d691c828a19bffd40e.png

题目描述:

在一个二维数组array中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数


0187e6e58da2440b9619836db3295bfd.png

bool Find(int target, int** array, int arrayRowLen, int* arrayColLen ) {
    // write code here
    int x=0;
    int y=*arrayColLen-1;
    while(x<=arrayRowLen-1&&y>=0)
    {
        if(array[x][y]>target)
        {
            y--;
        }
        else if(array[x][y]<target)
        {
            x++;
        }
        else
        {
            return true;
        }
    }
    return false;
}

关于我思考的两个问题:

  1. 查找一定程度上是排除法,一次能排除能几个有时候决定了时间复杂度
  2. 代码书写中while里是循环退出的条件,while里的if是对根据情况做出的调整。

3.寻找峰值

点我做题:寻找峰值

f4aa0c9f7a8a452694de4871f7f4d750.png

题目描述:

给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可,请使用O(logN)的时间复杂度实现此问题吗?

f32a7ae2fb80428d9845577e15ef2650.png


题解:a[mid]和a[mid+1]比较:

在这里我想说a[mid+1]在后面为什么也不会越界,因为mid即使是在只有两个元素的时候,mid也是==left,而在只有一个元素的时候,就是已经退出while,已经找到了峰值元素。

int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
    int left=0;
    int right=rotateArrayLen-1;
    while(left<right)
    {
        if(rotateArray[left]<rotateArray[right])
        {
            return rotateArray[left];
        }
        int mid=left+((right-left)>>1);//优先级
        if(rotateArray[mid]>rotateArray[right])
        {
            left=mid+1;
        }
        else if(rotateArray[mid]<rotateArray[right])
        {
            right=mid;
        }
        else
        {
            right--;
        }
    }
    return rotateArray[left];
}


4.旋转数组的最小数字

点我做题:旋转数组的最小数字


cab19560b03b434680b5fd775e874303.png

题目描述:


有一个长度为 n 的非降序数组,比如[1,2,3,4,5],将它进行旋转,即把一个数组最开始的若干个元素搬到数组的末尾,变成一个旋转数组,比如变成了[3,4,5,1,2],或者[4,5,1,2,3]这样的。请问,给定这样一个旋转数组,求数组中的最小值。


解题思路:本题特别说明非降序,就是说从后忘前是>=的关系,旋转后只是变成了两个非降序,那么只要找到


a[mid]和a[right]比较;


如果a[mid]>a[right],a[mid]到a[right]一定不是升序的,也就是a[mid]从升再到降到a[right],则最小值在右半边且a[mid]不在区间里,即更新为left=mid+1;


如果a[mid]<a[right],a[mid]到a[right]一定是升序的,也就是a[mid]从一直升到a[right],则最小值在左半边且a[mid]不在区间里,即更新为right=mid;


如果a[mid]==a[right],不一定!!!有可能最小值在左边,也有可能在右边,如下例子;

0bcf68666de94bba98adbdb22a21ecd4.png


654ddbfc39604639a65aba9f3d0eba22.png

int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {
    // write code here
    int left=0;
    int right=rotateArrayLen-1;
    while(left<right)
    {
        if(rotateArray[left]<rotateArray[right])
        {
            return rotateArray[left];
        }
        int mid=left+((right-left)>>1);//优先级
        if(rotateArray[mid]>rotateArray[right])
        {
            left=mid+1;
        }
        else if(rotateArray[mid]<rotateArray[right])
        {
            right=mid;
        }
        else
        {
            right--;
        }
    }
    return rotateArray[left];
}

6.求平方根

点我做题:求平方根


c83c9fe848c74abab31e4cad3fb82c02.png

int Sqrt(int x ) {
    // write code here
    if(x==0) return 0;
    if(x==1) return 1;
    int left=1;
    int right=x;
    while(left<=right)
    {
        int mid=(left+right)>>1;
        if(mid<=x/mid&&(mid+1)>x/(mid+1))
        {
            return mid;
        }
        else if(mid<x/mid)
        {
            left=mid+1;
        }
        else if(mid>x/mid)
        {
            right=mid-1;
        }
    }
    return 0;
}

5.总结


查找算法,O(logN),优先考虑二分查找

while(left<right)还是while(left<=right),得到的是相等的时候是在外面还是里面

缩小后的区间和原区间特征是相同的

if判断条件最难找,也就是二分查找的关键

if花括号里的更新得看mid是否可以排除在新区间外


fe3525c09fb349b9ac315a862c20a660.png


还是得多画图啊!


最后:这波虽然只有4道关于二分查找的题,是不是不过瘾呐?点击链接做牛客网算法题


目录
相关文章
|
1月前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩分享分库分表的基因算法设计,涵盖分片键选择、水平拆分策略及基因法优化查询效率等内容,助力面试者应对大厂技术面试,提高架构设计能力。
美团面试:百亿级分片,如何设计基因算法?
|
1月前
|
算法 前端开发 Java
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
这篇文章总结了单链表的常见面试题,并提供了详细的问题分析、思路分析以及Java代码实现,包括求单链表中有效节点的个数、查找单链表中的倒数第k个节点、单链表的反转以及从尾到头打印单链表等题目。
32 1
数据结构与算法学习四:单链表面试题,新浪、腾讯【有难度】、百度面试题
|
25天前
|
机器学习/深度学习 算法 Java
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
机器学习、基础算法、python常见面试题必知必答系列大全:(面试问题持续更新)
|
30天前
|
算法 Java 数据库
美团面试:百亿级分片,如何设计基因算法?
40岁老架构师尼恩在读者群中分享了关于分库分表的基因算法设计,旨在帮助大家应对一线互联网企业的面试题。文章详细介绍了分库分表的背景、分片键的设计目标和建议,以及基因法的具体应用和优缺点。通过系统化的梳理,帮助读者提升架构、设计和开发水平,顺利通过面试。
美团面试:百亿级分片,如何设计基因算法?
|
1月前
|
算法 C# 索引
C#二分查找算法
C#二分查找算法
|
1月前
|
算法 Java 数据中心
探讨面试常见问题雪花算法、时钟回拨问题,java中优雅的实现方式
【10月更文挑战第2天】在大数据量系统中,分布式ID生成是一个关键问题。为了保证在分布式环境下生成的ID唯一、有序且高效,业界提出了多种解决方案,其中雪花算法(Snowflake Algorithm)是一种广泛应用的分布式ID生成算法。本文将详细介绍雪花算法的原理、实现及其处理时钟回拨问题的方法,并提供Java代码示例。
67 2
|
1月前
|
数据可视化 搜索推荐 Python
Leecode 刷题笔记之可视化六大排序算法:冒泡、快速、归并、插入、选择、桶排序
这篇文章是关于LeetCode刷题笔记,主要介绍了六大排序算法(冒泡、快速、归并、插入、选择、桶排序)的Python实现及其可视化过程。
13 0
|
1月前
|
存储 算法 C语言
【C语言】二分查找算法
【C语言】二分查找算法
|
1月前
|
消息中间件 存储 算法
一文搞懂二分查找算法!
一文搞懂二分查找算法!
|
1月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
18 0