当前位置: 首页 > article >正文

Leetcode:34(二分查找)

一,题目

二,思路

  • 找到最左和最右俩个点,利用俩个二分查找
  • 俩种情况一种存在一种不存在
  • 存在:nums[m]==target右边-1  结果i
  • 存在:nums[m]==target左边+1  但是结果下标减去i-1
  • 上面俩种情况可以举例子 1 2 2 3 找2 自己推理一下就明白
  • 不存在:一种情况nums为空的情况 一种是数据没找到

三,代码

import java.util.Arrays;

public class Leetcode34 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Leetcode34().searchRange(new int[]{1}, 1)));
    }

    public int[] searchRange(int[] nums, int target) {
        int[] arr = new int[2];
        arr[0] = left(nums, target);
        if (arr[0] == -1)
            arr[1] = -1;
        else
            arr[1] = right(nums, target);
        return arr;
    }

    public int left(int[] nums, int target) {
        if (nums.length > 0) {
            int i = 0;
            int j = nums.length - 1;
            while (i <= j) {
                int m = (i + j) >>> 1;
                if (nums[m] < target) {//左
                    i = m + 1;
                } else {
                    j = m - 1;
                }
            }
            if (i < nums.length && nums[i] == target) return i;
        }
        return -1;
    }

    public int right(int[] nums, int target) {
        if (nums.length > 0) {
            int i = 0;
            int j = nums.length - 1;
            while (i <= j) {
                int m = (i + j) >>> 1;
                if (nums[m] <= target) {//左
                    i = m + 1;
                } else {
                    j = m - 1;
                }
            }
            if (i - 1 < nums.length && nums[i - 1] == target) return i - 1;
        }
        return -1;
    }
}


http://www.kler.cn/a/587456.html

相关文章:

  • Android(java)高版本 DownloadManager 封装工具类,支持 APK 断点续传与自动安装
  • C#结构体(Struct)详解
  • 学习MDA规范_9.CORBA(公共对象请求代理架构)‌
  • 「自动驾驶背后的数学:从传感器数据到控制指令的函数嵌套」—— 揭秘人工智能中的线性函数、ReLU 与复合函数
  • PostgreSQL数据库版本支持策略
  • camellia redis proxy v1.3.3对redis主从进行读写分离(非写死,自动识别故障转移)
  • CobaltStrike详细使用及Linux上线
  • 论Linux进程间通信
  • BGP实验(二)—路由反射器
  • 基于Spring Boot的小区疫情购物系统的设计与实现(LW+源码+讲解)
  • SOA(面向服务架构)与微服务架构的区别与联系
  • 企业为什么选择算力服务器?
  • MongoDB Vs Elasticsearch
  • 基于Python+SQLite实现(Web)验室设备管理系统
  • Linux 快捷键 | 终端快捷键 / 键盘快捷键
  • 9.贪心算法
  • C 语 言 --- 二 维 数 组 的 应 用
  • K8S学习之基础三十一:k8s中RBAC 的核心概念
  • 基于Matlab实现机械臂阻抗控制仿真
  • MinIo前后端实现