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

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

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道关于二分查找的题,是不是不过瘾呐?点击链接做牛客网算法题


目录
相关文章
|
2天前
|
算法 索引
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
【数据结构与算法 | 基础篇】力扣704/35/34:二分查找
|
3天前
|
机器学习/深度学习 算法 固态存储
深度学习算法工程师面试问题总结| 深度学习目标检测岗位面试总结
本文给大家带来的百面算法工程师是深度学习目标检测岗位面试总结,文章内总结了常见的提问问题,旨在为广大学子模拟出更贴合实际的面试问答场景。在这篇文章中,我们还将介绍一些常见的深度学习目标检测面试问题,并提供参考的回答及其理论基础,以帮助求职者更好地准备面试。通过对这些问题的理解和回答,求职者可以展现出自己的深度学习目标检测领域的专业知识、解决问题的能力以及对实际应用场景的理解。同时,这也是为了帮助求职者更好地应对深度学习目标检测岗位的面试挑战,提升面试的成功率和竞争力。
|
4天前
|
算法 搜索推荐 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(下)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
8 0
|
4天前
|
算法 程序员 索引
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(中)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
14 0
|
4天前
|
算法 C语言 C++
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题(上)
数据结构与算法⑥(第二章OJ题,下)后八道链表面试题
12 0
|
4天前
|
算法 测试技术
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题(下)
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题
11 0
|
4天前
|
算法
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题(上)
数据结构与算法⑤(第二章OJ题,上)前五道链表面试题
9 0
|
4天前
|
机器学习/深度学习 编解码 算法
算法工程师面试问题总结 | YOLOv5面试考点原理全解析
本文给大家带来的百面算法工程师是深度学习目标检测YOLOv5面试总结,文章内总结了常见的提问问题,旨在为广大学子模拟出更贴合实际的面试问答场景。在这篇文章中,我们还将介绍一些常见的深度学习目标检测面试问题,并提供参考的回答及其理论基础,以帮助求职者更好地准备面试。通过对这些问题的理解和回答,求职者可以展现出自己的深度学习目标检测领域的专业知识、解决问题的能力以及对实际应用场景的理解。同时,这也是为了帮助求职者更好地应对深度学习目标检测岗位的面试挑战,提升面试的成功率和竞争力。
|
7天前
|
算法 前端开发 Android开发
Android文字基线Baseline算法的使用讲解,Android开发面试题
Android文字基线Baseline算法的使用讲解,Android开发面试题
Android文字基线Baseline算法的使用讲解,Android开发面试题
|
7天前
|
算法 Java API
Groovy脚本基础全攻略,android面试算法题
Groovy脚本基础全攻略,android面试算法题