首页 > 其他分享 >二分查找

二分查找

时间:2024-09-01 18:26:27浏览次数:6  
标签:二分 right target nums int mid 查找 left

题目: 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

解法一:左闭右闭区间。(left = 0, right = nums.length - 1)
思路:对于这种问题,捕捉到数据类型是数组并且数组中元素是有序的并且是查找类首先想到使用二分查找来解决。首先找到数组的中间值,使用中间值与target进行比较,假如target小于nums[mid]代表target在中间值的左侧,所以我们排除掉一半的数据。之后继续重复之前的做法,逼近target即可。
在左闭右闭的条件下,左边界和右边界都是存在意义的,所以在循环条件中left在小于等于right的情况下都是有意义的。在target小于nums[mid]的情况下,移动右侧边界,right = mid - 1; 因为right是有意义的嘛,nums[mid]已经确实不是target的情况下要使用,right = mid - 1;来缩小范围。反之同理。
代码如下:

点击查看代码
class Solution {
    public int search(int[] nums, int target) {
        if(nums[nums.length - 1] < target || nums[0] > target) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left <= right) {
            int mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target) {
                right = mid - 1;
            }else {
                left = mid +1;
            }
        }
        return -1;
    }
}

解法二:左闭右开区间。(left = 0, right = nums.length)
思路:总体思路同解法一,但是right变成了开区间。使得mid也变成了开区间,在缩小边界赋值mid时不必对right - 1,使用right就可以了。在循环条件中left也始终小于right.
代码如下:

点击查看代码
class Solution {
    public int search(int[] nums, int target) {
        if (nums[nums.length - 1] < target || nums[0] > target) {
            return -1;
        }
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return -1;
    }
}

标签:二分,right,target,nums,int,mid,查找,left
From: https://www.cnblogs.com/dreamlife2491/p/18391537

相关文章

  • WPF Material Design中资源的查找和使用
    MaterialDesign中,一共分为两大块。一个是颜色资源,一个是控件资源。下面来说下,如何使用控件资源:在VS中,通过Nuget添加完MaterialDesign后,还需要在App.xaml中引用这些资源,引用的方法如下图所示:在1处,引入materialdesign的引用。在2处,可以修改项目的主题色,这个比较重要。以前......
  • 信息学奥赛初赛天天练-81-NOIP2015普及组-完善程序-二分答案、二分查找、中位数、二分
    1完善程序(单选题,每小题3分,共30分)中位数median给定n(n为奇数且小于1000)个整数,整数的范围在0∼m(0<m<2^31)之间,请使用二分法求这n个整数的中位数。所谓中位数,是指将这n个数排序之后,排在正中间的数。(第五空2分,其余3分)01#include<iostream>02usingnamespace......
  • 学习笔记(?):一类查询 kth 的整体二分 trick
    问题大概就是有若干次修改(也有可能没有)和若干次查询,查询形如查某个范围的kth。做法是,把可能成为答案的候选集合按照权值大小排序。询问集合可以不用管顺序。然后开始二分。我们令solve(l,r,L,R)表示第\(l\)到\(r\)个询问的kth一定在候选序列的第\(L\)到\(R\)个数。......
  • NC 二分查找-II
    系列文章目录文章目录系列文章目录前言前言前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。描述请实现有重复数字的升序数组的二分查找给定一个元素有序的(升序)长......
  • 【Python-办公自动化】1秒解决海量查找替换难题
    欢迎来到"花花ShowPython",一名热爱编程和分享知识的技术博主。在这里,我将与您一同探索Python的奥秘,分享编程技巧、项目实践和学习心得。无论您是编程新手还是资深开发者,都能在这里找到有价值的信息和灵感。自我介绍:我热衷于将复杂的技术概念以简单易懂的方式呈现给大家,......
  • [Python手撕]二分法
    二分法二分法的几个位置比如01234567891233333456有时候想要寻找小于3的最大数字有时候想要寻找第一个满足>=3的数字,有时候想要寻找最后一个满足>=3的数字,有时候想要寻找小于4的最大数字nums=[1,2,3,4,5,5,5,5,5,6,7,8,9]n=......
  • F. Final Boss(二分,周期)
    题目来源:https://codeforces.com/contest/1985/problem/F//题意:你有n种攻击,每种攻击有周期和攻击力,如果当前回合是x,以为着第i种攻击,下次攻击是x+ci回合。现在有Boss,生命值为h,当h<=0的时候,Boss死亡。一开始所有攻击都没有冷却时间,问最少第几回合Boss死亡。//思路:“最开始无脑模......
  • PowerShell Select-String:在字符串和文件中查找文本
    语法Select-String[-Culture<String>][-Pattern]<String[]>[-Path]<String[]>[-SimpleMatch][-CaseSensitive][-Quiet][-List][-NoEmphasis][-Include<String[]>][-Exclu......
  • 【信息收集】查找真实ip
    一、多地ping确认是否使用CDN二、查询历史DNS解析记录2.1DNSDB2.2微步在线2.3Ipip.net2.4viewdns三、phpinfo四、绕过CDN如果目标网站使用了CDN,使用了cdn真实的ip会被隐藏,如果要查找真实的服务器就必须获取真实的ip,根据这个ip继续查询旁站。注意:很......
  • 二分法查+范围内临近值查找
        1uint16FindPosition(uint8arr[],uint16length,uint8target)2{3uint16low=0;4uint16high=length-1;5uint16closest_position=0xFFFF;67if(target<arr[0]||target>arr[length-1])8{9......