首页 > 其他分享 >LeetCode 704.二分查找

LeetCode 704.二分查找

时间:2024-04-05 12:29:43浏览次数:24  
标签:二分 right target nums 704 middle int LeetCode left

一、题目

二、解题

注:本文均是Java代码

1、双闭区间写法

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int middle = (left + right) >>> 1;
            if (target < nums[middle]) {
                right = middle - 1;
            }
            else if (nums[middle] < target) {
                left = middle + 1;
            }
            else {
                return middle;
            }
        }
        return -1;
    }    
}

2、左闭右开区间写法

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int middle = (left + right) >>> 1;
            if (target < nums[middle]) {
                right = middle;
            }
            else if (nums[middle] < target) {
                left = middle + 1;
            }
            else {
                return middle;
            }
        }
        return -1;
    }    
}

3、左开右闭区间写法

class Solution {
    public int search(int[] nums, int target) {
        int left = -1, right = nums.length - 1;
        while (left < right) {
            int middle = (left + right + 1) >>> 1;
            if (target < nums[middle]) {
                right = middle - 1;
            }
            else if (nums[middle] < target) {
                left = middle;
            }
            else {
                return middle;
            }
        }
        return -1;
    }    
}

4、双开区间写法


    public int search(int[] nums, int target) {
        int left = -1, right = nums.length;
        while (left + 1 < right) {
            int middle = (left + right) >>> 1;
            if (target < nums[middle]) {
                right = middle;
            }
            else if (nums[middle] < target) {
                left = middle;
            }
            else {
                return middle;
            }
        }
        return -1;
    }    
}

5、说明

四种写法本质上并没有太大差别,只是定义的区间开闭不同,在解决一些具体问题的时候可以根据题目定义不同开闭区间,使用技巧快速解题。

尤其注意左开右闭和左闭右开区间的偏移问题。

最容易出现的两个报错就是数组越界和死循环超时。

—定要记住最基础版的双闭区间写法,其它写法都是根据这个的变形。

参考博客:

【玩转二分查找Ⅰ】左闭右闭型,左开右闭型,左闭右开型(动图演绎)_数学左闭右开-CSDN博客

二分查找的细节(左闭右闭、左闭右开、左开右闭)及其两段性-CSDN博客

参考视频:

二分查找为什么总是写错?_哔哩哔哩_bilibili

二分查找 红蓝染色法_哔哩哔哩_bilibili

搜索旋转排序数组【基础算法精讲 05】_哔哩哔哩_bilibili

标签:二分,right,target,nums,704,middle,int,LeetCode,left
From: https://blog.csdn.net/qq_63939626/article/details/137353961

相关文章

  • 二分板子
    二分板子#include<iostream>constexprintN=100;intmain(){inta[N];intn;std::cin>>n;for(inti=0;i<n;i++)std::cin>>a[i];intl=0,r=n-1;intt;std::cin>>t;while(l<r){......
  • LeetCode 1539. Kth Missing Positive Number
    原题链接在这里:https://leetcode.com/problems/kth-missing-positive-number/description/题目:Givenanarray arr ofpositiveintegerssortedina strictlyincreasingorder,andaninteger k.Return the kth positive integerthatis missing fromthisarra......
  • 【leetcode面试经典150题】12.O(1) 时间插入、删除和获取随机元素(C++)
    【leetcode面试经典150题】专栏系列将为准备暑期实习生以及秋招的同学们提高在面试时的经典面试算法题的思路和想法。本专栏将以一题多解和精简算法思路为主,题解使用C++语言。(若有使用其他语言的同学也可了解题解思路,本质上语法内容一致)【题目描述】实现RandomizedSet 类:......
  • LeetCode in Python 88. Merge Sorted Array (合并两个有序数组)
    合并有序数组也有两种方法,区别是空间复杂度不同。第一种,重新开辟一个数组空间,大小为O(m+n),另外需要三个指针分别指向两个有序数组和新开辟的数组,依次判断两个数组内元素大小,不断更新指针即可。第二种,无需单独开辟空间,在第一个数组(该数组空间足够存放两个数组总长的数据)内进行......
  • 代码随想录算法训练营第一天 | 704.二分查找、27.移除元素
    704.二分查找文档讲解:代码随想录(https://www.programmercarl.com/)视频讲解:https://www.bilibili.com/video/BV1fA4y1o715/状态:704有思路但是不完善题目给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下......
  • 二分答案跳石头游戏
    步骤: 输入:用户输入了三个整数,分别表示石头的总长度l,石头的数量n,以及最多可以撤去的石头数量m。初始化石头位置数组:创建一个长度为n+2的数组arr,用于存储每块石头的位置。数组的第一项和最后一项分别表示起点和终点的位置,因此初始化为0和l。计算最小相邻石头间距:循环......
  • C语言 | Leetcode C语言题解之第8题字符串转换整数atoi
    题目:题解:intmyAtoi(char*s){inti=0;intout=0;intpol=1;intlen=strlen(s);if(len==0)return0;while(s[i]=='')i++;//删除空格if(s[i]=='-'){//判断正负pol=-1;i++;}else......
  • 【leetcode】将x减到0的最小操作数/水果成篮/找到字符串中所有字母异位词{史上最容易
    文章目录1.将x减到0的最小操作数2.水果成篮3.找到字符串中所有字母异位词1.将x减到0的最小操作数分析题目x不断地减去数组两端的值看能否减到0;是不是就是在问:nums数组中存不存在【左端+右端】组成的连续区间,区间上数的和为x继续分析==》是不是就是在问:nums......
  • Java | Leetcode Java题解之第10题正则表达式匹配
    题目:题解:classSolution{publicbooleanisMatch(Strings,Stringp){intm=s.length();intn=p.length();boolean[][]f=newboolean[m+1][n+1];f[0][0]=true;for(inti=0;i<=m;++i){......
  • Java | Leetcode Java题解之第9题回文数
    题目:题解:classSolution{publicbooleanisPalindrome(intx){//特殊情况://如上所述,当x<0时,x不是回文数。//同样地,如果数字的最后一位是0,为了使该数字为回文,//则其第一位数字也应该是0//只有0满足这一属......