首页 > 其他分享 >建立“二分查找”的通用模型

建立“二分查找”的通用模型

时间:2024-09-14 15:24:16浏览次数:10  
标签:二分 right target nums int 模型 mid 查找 left

案例

[5, 7, 7, 8, 8, 10]

返回非递减数组中第一个 ≥8 的数的位置,如果所有数都<8,返回数组长度

暴力做法:遍历每个数,询问是否 ≥8? 时间复杂度 O(n)

二分查找的模型

红蓝染色法:约定如下

≥ target 表示在 target 右侧标记为蓝色

< target 表示在 target 左侧标记为红色

1. 左闭右闭

func lowerBound(nums []int, target int) int {
    left := 0
    right := len(nums) - 1
    // 闭区间[left, right]
    for left <= right {  // 区间不为空,继续轮询查询目标
        // right - left 防止溢出
        mid := left + (right - left) / 2
        /*
        循环不变量(即通过这次循环可以得知的具体不变的信息)
        nums[left] < target
        nums[right] >= target
        */
        if nums[mid] >= target {
            // 范围缩小到[left, mid-1]
            right = mid - 1
        } else {
            // 范围缩小到(mid+1, right)
            left = mid + 1
        }
    }

    // 此时 left 等于 right + 1
    // 因为 nums[left - 1] < target 且 nums[left] >= target,所以答案是 left  / right + 1
    return left
}

2. 左闭右开

func lowerBound(nums []int, target int) int {
    left := 0
    right := len(nums)
    // 左闭右开[left, right)
    for left < right {  // 区间不为空,继续轮询查询目标
        // right - left 防止溢出
        mid := left + (right - left) / 2
        /*
        循环不变量(即通过这次循环可以得知的具体不变的信息)
        nums[left] < target
        nums[right] >= target
        */
        if nums[mid] >= target {
            // 范围缩小到[left, mid)
            right = mid
        } else {
            // 范围缩小到(mid+1, right)
            left = mid + 1
        }
    }

    // 此时 left 等于 right
    // 因为 nums[left - 1] < target 且 nums[left] >= target,所以答案是 left  / right
    // 循环结束后 left == right
    return left
}

3. 左开右开


func lowerBound(nums []int, target int) int {
    left := -1
    right := len(nums)
    // 开区间 (left, right)
    for left + 1 < right {  // 区间不为空,继续轮询查询目标
        // right - left 防止溢出
        mid := left + (right - left) / 2
        /*
        循环不变量(即通过这次循环可以得知的具体不变的信息)
        nums[left] < target
        nums[right] >= target
        */
        if nums[mid] >= target {
            // 范围缩小到(left, mid)
            right = mid
        } else {
            // 范围缩小到(mid, right)
            left = mid
        }
    }

    // 此时 left 等于 right - 1
    // 因为 nums[right - 1] < target 且 nums[right] >= target,所以答案是 right
    return right
}

4. 总结

1. 左闭右闭

left=0, right=len(nums)-1

区间不为空的循环条件:left ≤ right

mid ≥ target: right = mid - 1

mid < target: left = mid + 1

2. 左闭右开


left = 0, right = len(nums)

区间不为空的循环条件: left < right

mid ≥ target: right = mid

mid < target: left = mid + 1

3. 左开右开


left = -1, right = len(nums)

区间不为空的循环条件:left + 1 < right

mid ≥ target: right = mid

mid < target: left = mid

举一反三

1. 获取第一个大于等于 target

ans = f(x)

2. 获取第一个大于 target

ans = f(x+1)

3. 获取最后一个小于 target

ans = f(x) - 1

4. 获取最后一个小于等于 target

ans = f(x+1)-1


func TestLowerBound(t *testing.T) {
	nums := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

	target := 5
	// 找第一个大于等于 target 的下标  5

	fmt.Println(lowerBound(nums, target))

	// 找第一个大于 target 的下标  6

	fmt.Println(lowerBound(nums, target+1))

	// 找最后一个小于等于 target 的下标 5

	fmt.Println(lowerBound(nums, target+1) - 1)

	// 找最后一个小于 target 的下标  4

	fmt.Println(lowerBound(nums, target) - 1)
}

题目

以如下题目,来分析二分查找的多种模型(固定模式)

34. 在排序数组中查找元素的第一个和最后一个位置

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

使用二分查找模型解决相关题目 ➡️

参考

【0x3f-灵神基础算法精讲 04】

标签:二分,right,target,nums,int,模型,mid,查找,left
From: https://www.cnblogs.com/panlq/p/18414075

相关文章

  • 代数模型(Algebraic Models)---线性规划------+ 案例 + Python源码求解(见文中)
    目录一、代数模型(AlgebraicModels)详解1.1什么是代数模型?1.2代数模型的基本形式1.3安装所需要的Python包--运行下述案例1.4代数模型的应用案例案例1:市场供需平衡模型Python求解代码Python求解结果如下图:案例2:运输问题中的线性规划模型进行数学建模分析1.目标函数2.......
  • 几何概率模型
    一、几何概率模型①样本空间的样本点为无限个②每个样本点发生的可能性是均等的③P(A)=事件A的几何度量值/样本空间的几何度量值说明:如果样本空间的样本点为有限个,则为古典概型通过2个例子,来感受下两者的区别①例:在[1,4]区间内,任意取一个整数,求该整数<2的概率设:事件A为整数<2第1......
  • 大语言模型(LLM)入门学习路线图
    Github项目上有一个大语言模型学习路线笔记,它全面涵盖了大语言模型的所需的基础知识学习,LLM前沿算法和架构,以及如何将大语言模型进行工程化实践。这份资料是初学者或有一定基础的开发/算法人员入门活深入大型语言模型学习的优秀参考。这份资料重点介绍了我们应该掌握哪些核......
  • AI跟踪报道第56期-新加坡内哥谈技术-本周AI新闻: 划时代 Open AI 新模型系统2思维推理
      每周跟踪AI热点新闻动向和震撼发展想要探索生成式人工智能的前沿进展吗?订阅我们的简报,深入解析最新的技术突破、实际应用案例和未来的趋势。与全球数同行一同,从行业内部的深度分析和实用指南中受益。不要错过这个机会,成为AI领域的领跑者。点击订阅,与未来同行!订阅:https://......
  • Flux.1 的专属提示词增强模型来啦!不用费脑,一键扩写提示词!
    编写提示词对于听雨来说一直是一个比较费脑子的事情,下班以后的闲暇时间本就不多,还要费脑子在提示词上,让本就不够富裕的脑子更加不堪重负!所以听雨对于提示词相关的插件都是蛮感兴趣的,毕竟可以让一天紧张工作疲惫不堪的脑子偷个懒,何乐而不为嘞!之前听雨也介绍了一款随机提示词插......
  • 二分系列(二分答案)9/14
    一、使结果不超过阈值的最小除数给你一个整数数组 nums 和一个正整数 threshold  ,你需要选择一个正整数作为除数,然后将数组里每个数都除以它,并对除法结果求和。(除法结果会向上取整7/3=3)请你找出能够使上述结果小于等于阈值 threshold 的除数中 最小 的那个。思路:......
  • Hume AI 推出 EVI 2 情感模型;OpenAI o1 模型问世,模拟人类思考问题 丨 RTE 开发者日报
       开发者朋友们大家好: 这里是「RTE开发者日报」,每天和大家一起看新闻、聊八卦。 我们的社区编辑团队会整理分享RTE(Real-TimeEngagement)领域内「有话题的新闻」、「有态度的观点」、「有意思的数据」、「有思考的文章」、「有看点的会议」,但内容仅代表编辑的个......
  • 专业角度深入讲解:大模型备案(生成式人工智能)
    一、什么是大模型备案?大模型备案是指大模型产品在向公众开放及商用之前,经过国家互联网信息办公室(简称“网信办”)等监管部门的备案审批过程。 是为加强生成式人工智能服务的合规管理,通过备案制度,促进人工智能技术的健康发展,建立起一个既安全又可靠的人工智能服务体系,为公众提供高......
  • 开源模型应用落地-qwen2-7b-instruct-LoRA微调-unsloth(让微调起飞)-单机单卡-V100(十七)
    一、前言  本篇文章将在v100单卡服务器上,使用unsloth去高效微调QWen2系列模型,通过阅读本文,您将能够更好地掌握这些关键技术,理解其中的关键技术要点,并应用于自己的项目中。  使用unsloth能够使模型的微调速度提高2-5倍。在处理大规模数据或对时间要求较高的场景下......
  • 智能工厂的设计软件 之 0之 Ⅰ AI模型:追求普智(普适智慧)的 现实模型
    写在讨论前面本期主题”智能工厂的设计软件”即 “程序”--“程序”做为”智能工厂的设计软件”的目的。前面的文章将这一主题称为“智能工厂的程序设计”是相对狭义一些的表述。1、文题中的数字(" 0 之 Ⅰ") 0:  “AI模型”的 “程序”性能层级  Layer-0( ......