返回值应插入位置的索引的二进制搜索
二进制搜索（Binary Search）是一种在有序数组中查找特定元素的搜索算法。其基本思想是通过每次比较数组中间元素与目标值，逐步缩小搜索范围，直到找到目标值或确定目标值不存在。
基础概念
- 有序数组：二进制搜索要求数组是有序的。
- 中间索引：每次搜索时，取数组的中间索引
mid = (low + high) / 2。 - 比较：比较中间元素与目标值，根据比较结果调整搜索范围。
优势
- 时间复杂度：O(log n)，比线性搜索快得多。
- 效率高：适用于大数据集。
类型
- 递归实现：通过递归调用自身来缩小搜索范围。
- 迭代实现：使用循环来缩小搜索范围。
应用场景
- 数据库索引：快速查找数据。
- 文件系统：快速定位文件。
- 算法竞赛：常见的问题解决方法。
示例代码（递归实现）
def binary_search(arr, target, low, high):
if high >= low:
mid = (high + low) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
return binary_search(arr, target, low, mid - 1)
else:
return binary_search(arr, target, mid + 1, high)
else:
return -1
# 示例数组
arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(arr, target, 0, len(arr) - 1)
if result != -1:
print("元素在索引 %d 处找到" % result)
else:
print("元素不在数组中")示例代码（迭代实现）
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# 示例数组
arr = [2, 3, 4, 10, 40]
target = 10
result = binary_search(arr, target)
if result != -1:
print("元素在索引 %d 处找到" % result)
else:
print("元素不在数组中")可能遇到的问题及解决方法
- 数组未排序：二进制搜索要求数组是有序的，如果数组未排序，需要先进行排序。
- 数组未排序：二进制搜索要求数组是有序的，如果数组未排序，需要先进行排序。
- 目标值不存在：如果目标值不存在于数组中，二进制搜索会返回
-1。 - 整数溢出：在计算中间索引时，可能会出现整数溢出问题。
- 整数溢出：在计算中间索引时，可能会出现整数溢出问题。
参考链接
通过以上信息，你应该对二进制搜索有了全面的了解，并且能够解决相关的问题。
相关·内容
我需要做一个二进制搜索，除了正常的函数之外，当没有找到值时，它会返回索引，我必须在索引中插入一个新的元素进行排序。在下面的代码中，第二个for用来搜索要交换的元素所在的索引。我需要做一个函数，将其替换为二进制搜索。这个方法看起来像什么？inserted
for (i = j-1; i >= 0 && v[i] > x; --i)
浏览 20提问于2020-11-09得票数 1
1回答
我正在尝试为排序数组实现一个insert对象，该数组使用二进制搜索来找到正确的索引来放置一个新对象。return 1; return -1; return 0; };要查找索引last = middle - 1; first = middle + 1; }
}
最后，我尝试找到正确<
浏览 2提问于2020-09-07得票数 2
回答已采纳
5回答
给定一个从1到10^5 (不重复)的输入流，我们需要能够在每个点上知道以前遇到过多少个比这个小的数字。为了更有效地完成这一任务，我可以维护其他数据结构或遵循其他算法吗？编辑：找到了一个与芬威克树有关的老问题，在这里很有帮助。顺便说一
浏览 6提问于2015-10-09得票数 5
我正在创建一个程序，它执行二进制和顺序，并绘制每次搜索的迭代。然而，我正在尝试使用一个内置的java搜索Collections.binarySearch(list,index)，返回值是我正在搜索的值的索引/位置。有没有可能使返回值成为计数器/迭代？
浏览 1提问于2019-08-15得票数 1
2回答
我试图使用Arrays.binarySearch()在int数组中搜索值，并且我知道如果值在数组中会找到，则该方法返回值的索引号，如果数组不包括值，则方法返回负数。这是我的数组：searchInArray = new int[]{2,3,4,22,1,2};int result1=
浏览 2提问于2014-03-08得票数 2
回答已采纳
3回答
查找插入位置
、、、、
我有一个整数的排序ArrayList。现在我有一个新的整数要插入到ArrayList中。这个新的整数必须插入到适当的位置，以保持ArrayList的排序顺序。我可以简单地将整数相加，然后使用Collections.sort( ArrayList )对其进行排序，但由于ArrayList太大，这种排序需要时间，并且需要多次插入，所以我不想多次排序，这会占用我的时间我可以有更少的时间，或者我可以手动<e
浏览 3提问于2013-10-07得票数 0
2回答
问题是如何找到插入点。我在纸上做了一些手工追踪，最后我观察到的是下限和上界相等，当它们相等时，插入点总是高于下界和上界的指数。我知道网上有很多解决方案，但是我真的在尝试自己去理解这个问题，因为我只在自己学习的时候去学习和记住一些事情，而不是试图弄清楚别人是如何想出一个解决方案的。
如果有人能引导我，那就太好了。而且，一旦我得到插入点，我就可以做剩下的工作，这就是移动所有的值，一个更低的索引，以使插入
浏览 0提问于2014-07-21得票数 0
回答已采纳
所以我决定使用LinkedList<T>，，因为它在插入操作中是有效的。但在找到合适的地点时，似乎要花更长的时间。我用线性搜索来得到位置。如果我使用二进制搜索获得适当的位置使用ElementAt方法，它会提高性能吗？根据的说法，它仍然是一个O(n)操作。你认为如何？如果是这样的话，工作中还有其他更好的数据结构吗？因为如果我使用不同的数据结构，当向中间<
浏览 8提问于2012-10-15得票数 2
5回答
我有一个值列表(一维)，我想知道用来查找最接近查询值的最佳数据结构/算法。大多数解决方案(所有？)我发现这里的问题是针对2个或更多维度的。有没有人能给我建议我的案例的方法？我的直觉告诉我对数据进行排序，并以某种方式使用二进制搜索。顺便说一句，对于任何所需的树，都没有构造或插入时间的限制，所以可能有人会建议一种比简单的排序列表更好的树。
浏览 1提问于2010-07-19得票数 9
回答已采纳
我使用bisect_right()在一个txt文件中进行搜索。文本文件中的每一行都包含以下字符串"word1 word2 (tab) number“。也就是说，由空格(word1和word2)、制表符和数字分隔的两个单词。我将该文件作为一个带有readline()的列表读取。我使用带有参数"word1 word2“(word1 (空白)word2)的bisect_right来查找列表中找到(子)字符串"word1 word2”的索引。bis
浏览 1提问于2011-10-19得票数 0
我有如下的ViewModel类：{}
{ string Name { get; }集合按显示在UI中的名称排序。按名称重新排序我的收藏的最有效方法是什么，以便新项目出现在列表中的正确位置
浏览 3提问于2010-12-13得票数 2
回答已采纳
这个方法只是获取一个元素，并将其插入到已经排序的数组中的排序位置。但看起来这比它应该采取的步骤要多得多。有没有一种更高效、更高效的方法来做到这一点？
浏览 1提问于2011-06-21得票数 1
回答已采纳
1回答
我应该创建两个方法:第一个方法，bSearch，是一个二进制搜索算法。第二种方法，insertInOrder，应该采用我们从bSearch方法中得到的索引，并在数组中找到索引，通过将该数组的所有其他元素移到上面，打开该索引的一个点，并在该索引处插入键/ int。ints将从包含25个ints的文本文件中接收。我不准备做任何拷贝或额外的数组来完成这个任务，我应该在inser
浏览 1提问于2016-10-05得票数 2
回答已采纳
1回答
混合数据结构对效率的影响
、、、、
它应该可以作为链接列表使用，并从其继承来构造索引队列和索引堆栈。您可能会假设，将放入此数据结构中的所有内容都是可比较的，因此索引树将充当二进制搜索树。您应该构建一个迭代器类，以促进与此数据结构的交互。可以在列表迭代器指定的位置“之后”插入列表(有时可以通过find方法返回)。当然，在继承的索引队列中，插入将只位于队列的后面，但是
浏览 3提问于2014-07-22得票数 2
回答已采纳
3回答
我想编写一段代码，以便在适当的位置将一个数字插入排序数组(即数组在插入后仍然保持排序)。我打算这样做：
还有其他更好的方法吗？
浏览 9提问于2010-06-07得票数 5
回答已采纳
然后保持原始表按ID排序，并仅将索引用作原始表中二进制搜索的起始位置。
添加新记录的函数现在必须按ID执行二进制搜索，以查找插入新行的位置，并使索引更新。为了获得按分数排序的第一项，我们在索引表中查找分数(2，8)的第一行，并使用索引(2)作为表中二进制搜索的</em
浏览 0提问于2013-03-03得票数 3
回答已采纳
我试着用java代码将一个新元素插入到数组中，除了一行代码：“index= -index-1;”，我理解了大部分程序。为什么在索引前面使用负号？以下是完整的程序：}
我需要知道为什
浏览 6提问于2017-06-09得票数 0
回答已采纳
1回答
其思想是使用长度为2^k的多个数组存储n个元素，根据n.Each数组的二进制表示进行排序，不以任何方式排列不同的数组。更详细：让我们假设我们有一个长度为2^k的垂直数组，并在该数组的每个节点上附加长度为2^k的水平数组。因此，首先
浏览 2提问于2010-04-08得票数 2
3回答
如何对用于二进制搜索的字符串数组进行排序。在下面，我总是收到一个负数作为我的索引，而不是正确的索引。请帮帮忙？如果单词不在数组中，则应返回-1。
浏览 2提问于2013-04-19得票数 1
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
