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

二分查找

时间:2023-01-01 15:56:07浏览次数:38  
标签:二分 int mid else ltarget while 查找

概念:

适用范围:
有序数组
在顺序查找的基础上改进,每次查找都是用mid

时间

\(O(logn)\)

算法


int l = 0,r = n-1;
while(l<=r){//这里因为用来等号下面就要用减或者加
  int mid = l + (r - l ) / 2;
  if(arr[mid]>target){
     r  = mid - 1;
  }else{
    l = mid + 1;
  }
}

//如果上面没等
int l = 0,r = n-1;
while(l<r){//这样当等的时候就会结束
  int mid = l + (r - l ) / 2;
  if(arr[mid]>target){
     r  = mid;
  }else{
    l = mid + 1;
  }
}

标签:二分,int,mid,else,ltarget,while,查找
From: https://www.cnblogs.com/tsqo/p/17018142.html

相关文章

  • 二分学习笔记
    写在前面:本文中的“单调”不包括“单调不变”。(我不说你们应该也不会想到)一、算法引入如果我们要用一个数列(各个位置要有相应的数字形式的下标,且我们的这个下标可为小数......
  • leetcode笔记——二分图
    785.判断二分图-力扣(LeetCode)二分图实际上就是这个图里所有的环都是偶数个边,一般采取染色法来做通过dfs判断每个节点与其邻居节点是否是同一种颜色,如果有的话,那就一定......
  • BM18 二维数组中的查找
    题目描述给定一个每个元素都是升序数组的二维数组和一个target,判断target是否在数组中返回boolean类型思路分析方法一:遍历每个元素,判断是否相等方法二:将数组拍平,也......
  • BM17 二分查找-I
    题目描述请实现无重复数字的升序数组的二分查找给定一个元素升序的、无重复数字的整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在......
  • 【题解】P3515 [POI2011]Lightning Conductor(二分栈/分治优化DP)
    [POI2011]LightningConductor题面翻译给定一个长度为\(n\)的序列\(\{a_n\}\),对于每个\(i\in[1,n]\),求出一个最小的非负整数\(p\),使得\(\forallj\in[1,n]\),都......
  • Linux&shell通过正则表达式查找文件练习
    linux&shell编程中通过正则表达式来匹配查找文件极大的提高查找效率。首先,解释一下下边出现的命令。linux部分:ls:查看文件夹内的命令。|:管道。grep:搜索后边匹配的字符......
  • 【题解】P1527 [国家集训队]矩阵乘法(整体二分)
    [国家集训队]矩阵乘法题目描述给你一个\(n\timesn\)的矩阵,不用算矩阵乘法,但是每次询问一个子矩形的第\(k\)小数。输入格式第一行有两个整数,分别表示矩阵大小\(n......
  • C# 在excel中查找及替换数据
    在使用Excel处理数据时,有时候工作表内容很多,如果手动地一行一行的找数据很难发现它们在哪个地方。微软Excel给我们提供了一个很强大的数据处理功能-查找和替换,通过这个功能,......
  • 力扣二分查找
    题目给定一个n个元素有序的(升序)整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果目标值存在返回下标,否则返回-1。示例1:输入:nums=[-1,......
  • 二分查找
    题目题目地址描述请实现无重复数字的升序数组的二分查找给定一个元素升序的、无重复数字的整型数组nums和一个目标值target,写一个函数搜索nums中的target,如果......