寻找一种更好的方法来减少数组并确定数字是否有序
，可以使用二分查找算法。
二分查找算法是一种高效的查找算法，适用于有序数组。它通过将数组分成两部分，并比较目标值与数组中间元素的大小关系，从而确定目标值可能存在的区间。然后再在目标值可能存在的区间中继续进行二分查找，直到找到目标值或确定目标值不存在。
二分查找算法的步骤如下：
- 初始化左指针left为数组的起始位置，右指针right为数组的结束位置。
- 计算中间位置mid，即mid = (left + right) / 2。
- 比较目标值与数组中间元素的大小关系：
- 如果目标值等于中间元素，则找到目标值，返回结果。
- 如果目标值小于中间元素，则目标值可能存在于左半部分，更新右指针right为mid - 1。
- 如果目标值大于中间元素，则目标值可能存在于右半部分，更新左指针left为mid + 1。
- 重复步骤2和步骤3，直到找到目标值或确定目标值不存在。
二分查找算法的时间复杂度为O(log n)，其中n为数组的长度。相比于线性查找算法的时间复杂度O(n)，二分查找算法具有更高的效率。
应用场景： 二分查找算法适用于有序数组，并且数组中的元素可以进行比较。它可以用于快速查找某个元素是否存在于数组中，或者确定某个元素在数组中的位置。
推荐的腾讯云相关产品： 腾讯云提供了多种云计算相关产品，其中包括云服务器、云数据库、云存储等。以下是一些相关产品的介绍链接地址：
- 腾讯云服务器（云主机）：https://cloud.tencent.com/product/cvm
- 腾讯云数据库：https://cloud.tencent.com/product/cdb
- 腾讯云对象存储（COS）：https://cloud.tencent.com/product/cos
请注意，以上推荐的腾讯云产品仅供参考，具体选择应根据实际需求进行评估和决策。
相关·内容
3回答
在二进制搜索中混淆什么时候使用左<右；左<=右；很少有更多
binary-search
我很难理解何时使用：
while (left < right ) {
}
与何时使用：
while (left <= right ) {
}
此外，在设置左右边界时，有时我们使用：
left = mid
有时我们用
left = mid + 1;
类似的
right = mid; vs
right = mid - 1;
在二元搜索的知识中，我缺少什么基本的知识吗？
浏览 1提问于2019-07-25得票数 19
回答已采纳
1回答
为什么我的二进制搜索被困在一个没完没了的循环？
java、binary-search
我只是突然出现在这里，希望我的小问题能得到一个快速的答案。我试图创建一个二进制搜索方法，但遇到了一些问题。我迭代地创建了它，而我的IDE(Intellij)显然不喜欢它。它让我陷入了一个无尽的循环中.嗯，你知道剩下的。有什么建议吗？
下面是我简单而又漂亮的代码片段：
static int searchIt(int[] arr, int target){
int left = 0;
int right = arr.length - 1;
while (left <=
浏览 4提问于2022-03-23得票数 0
回答已采纳
3回答
以中间元素为枢轴的快速排序
quicksort
我对快速排序的理解是
选择一个枢轴元素(在本例中，我选择中间元素作为枢轴)
在极值处初始化左指针和右指针。
找到比枢轴更大的枢轴左边的第一个元素。
类似地，查找比枢轴小的枢轴右侧的第一个元素。
交换元素在3和4中找到。
重复3,4,5，除非左>=右转。
对左和右子数组重复整个过程，因为支点现在放在它的位置上。
我确信我在这里遗漏了一些东西，而且非常愚蠢。但上面似乎并不适用于这个数组：
8,7,1,2,6,9,10,2,11 pivot: 6 left pointer at 8, right pointer at 11
2,7,1,2,6,9,
浏览 2提问于2015-01-11得票数 10
回答已采纳
2回答
从数组C++初始化平衡的二进制搜索树
c++、binary-search-tree
我试图编写一个递归遍历数组的函数，将值插入到树中，同时保持树的平衡。假设数组是排序的，并且我们知道它的大小。我知道我需要做的是从数组的中间开始，将这个值插入根中，然后取左半和右一半的中间，然后将这些插入根的左右节点，等等，直到数组被填充。递归是我想到的第一件事，我编写的代码是有意义的，但它似乎不像我想的那样工作。
我遇到的问题是，第一个和最后一个值没有被插入，我得到的节点在每个叶的左边和右边都有垃圾值，而不是空值。
节点的结构很简单(由指导员提供)：
/* A lightweight structure implementing a general binary tree node */
te
浏览 2提问于2014-02-09得票数 0
回答已采纳
2回答
什么是懒惰的二进制搜索？
binary-search、lazy-evaluation
我不知道术语“懒惰”二分搜索是否有效，但我正在查阅一些旧材料，我只想知道是否有人可以解释懒惰二分搜索的算法，并将其与非懒惰二分搜索进行比较。
比方说，我们有这样一组数字：
2, 11, 13, 21, 44, 50, 69, 88
如何使用惰性二进制搜索来查找数字11？
浏览 2提问于2011-05-11得票数 2
回答已采纳
2回答
子阵列求和解决方案
algorithm
我最近遇到了一个子数组求和问题的两个指针的解决方案，我不是很确定算法的正确性。子数组求和问题包括寻找一个求和等于某个目标值的子数组。我已经看到这个问题的解决方案使用哈希表，但我质疑这个其他解决方案的正确性。让我给你们举一个算法的例子。
假设您有一个数组1,3,2,5,1,1,2,3，目标值x= 8。
使用左指针和右指针来指示子数组的开始和结束。在每一步中，左指针向前移动一步，右指针向前移动，只要子数组sum至多是x。这就是算法对上述数组的处理方式。
[1,3,2,5,1,1,2,3]
l r
[1,3,2,5,1,1,2,3] ##The right pointer doesn'
浏览 0提问于2019-09-22得票数 0
2回答
在添加到二进制搜索树之前对数组进行排序
java、recursion、binary-search-tree
我有一个按A-Z顺序排列的字符串数组。我想知道对它们进行排序以获得平衡的二进制搜索树的最好方法。我最初的想法是将数组分为前半部分和后半部分，然后分别对它们进行排序。
难道我不能使用递归的方式将其一分为二，以获得树的下一个节点吗？我只是现在还不能完全理解它，我想我应该问问是否有人有什么想法。来引导我朝着正确的方向前进，或者提供一些例子。谢谢!
我正在使用我自己的BinaryTree类和BinaryTreeNode类。编辑：
public class BinaryTree {
private BinaryTreeNode root;
public void insert(String text)
浏览 0提问于2011-11-07得票数 0
回答已采纳
3回答
从排序数组创建二进制搜索树
binary-search-tree
我目前正在检查编码算法。如果我们有以下情况：
给定一个具有唯一整数元素的有序(升序)数组，编写了一个算法来创建高度最小的二进制搜索树。
建议使用以下代码作为解决方案：
TreeNode createMinimalBST(int arr[], int start, int end){
if (end < start) {
return null;
}
int mid = (start + end) / 2;
TreeNode n = new TreeNode(arr[mid]);
n.setLeftChild(createMinima
浏览 0提问于2017-07-01得票数 6
回答已采纳
1回答
二进制搜索Python
python、beginner、binary-search
试着做一个二进制搜索算法，我做得怎么样？
def homogeneous_type(list1):
i_list = iter(list1)
listtype = type(next(i_list))
return True if all(isinstance(x, listtype) for x in i_list) else False
def binSearch(list1, value):
if not list1:
raise ValueError("list is empty")
if not homo
浏览 0提问于2018-09-13得票数 0
回答已采纳
1回答
动态数组未正确初始化
c++、arrays、dynamic、mergesort
我正在编写一个程序，它使用两个动态数组对原始数组进行排序:一个用于左侧，一个用于右侧。
但是，动态数组不接收第23行和第28行的原始数组(正如整个数组中的cout方法所演示的那样)。它们要么是空的，要么包含超出边界的元素。因此，程序不能作为一个整体工作。我的问题是，是初始化本身有问题，还是第18-19行的声明有问题？我个人认为它是声明，但我不确定我应该如何处理它，因为对于动态数组，我不想太多地扰乱大小。我包含了正确测试的所有方法，但如果它们被认为是不必要的，我将编辑这个问题。提前感谢您的帮助。
#include "stdafx.h"
#include <iostream&
浏览 1提问于2014-04-10得票数 1
3回答
二进制搜索开始或结束是目标
binary-search
为什么当我看到二进制搜索的示例代码时，从来没有一个if语句来检查数组或结束的开始是目标？
import java.util.Arrays;
public class App {
public static int binary_search(int[] arr, int left, int right, int target) {
if (left > right) {
return -1;
}
int mid = (left + right) / 2;
if (target == a
浏览 5提问于2021-09-29得票数 1
回答已采纳
2回答
求递增递减阵中的最大元
c、array、interview-questions、binary-search
问题:查找列表中最大的部分，该列表存储为两个部分，一个按升序存储，另一个按降序存储。元素是不同的。
输入[2 3 4 5 6 7 10 9 8 7]
输出：10
我的解决方案如下。在我的单元测试中工作。想知道从编码的角度看是否有什么改进(尤其是在面试中被问到)。
long getMaxIndex(long *arr, size_t size)
{
long left = 0;
long right = size - 1;
if (arr == nil) return 0;
while (left < right)
{
long
浏览 0提问于2016-10-02得票数 4
请描述您的问题
标题：FTP Server 工具 - 对象存储 - 产品文档 - 帮助与文档 - 腾讯云
地址：https://cloud.tencent.com/document/product/436/7214
浏览 504提问于2018-02-23
8回答
给定一个双离子阵列和数组中的元素x，在2log(n)时间内找到x的索引。
algorithm、search
首先，针对这个问题定义了一个双元数组，使得对于长度为N的数组中的某个索引N，0 < K < N - 1和0到K是一个单调递增的整数序列，K到N-1是一个单调递减的整数序列。
例子：[1, 3, 4, 6, 9, 14, 11, 7, 2, -4, -9].它从1单调增加到14，然后从14下降到-9。
这个问题的前身是在3log(n)中解决它，这要容易得多。一个改变的二进制搜索找到最大的指数，然后两个二进制搜索分别对0到K和K+1到N-1。
我假设2log(n)中的解决方案需要您解决问题，而不需要找到最大值的索引。我考虑过重叠二进制搜索，但除此之外，我不知道如何向前迈进。
浏览 6提问于2013-10-15得票数 26
回答已采纳
2回答
旋转排序数组中的最小值
arrays、algorithm、binary-search
我在看挑战：
假设一个按升序排序的数组在预先不为您所知的某个支点旋转。
(即[0,1,2,4,5,6,7]可能变成[4,5,6,7,0,1,2])。
找到最小的元素。
您可以假设数组中不存在重复。
我找到了这个解决方案
function findMin(nums) {
if (nums.length === 1) { //Edge
return nums[0];
}
let left = 0, right = nums.length - 1 //Two pointers
if (nums[right] > nums[0]) {
浏览 0提问于2020-10-14得票数 0
1回答
3和算法复杂度
c、time-complexity
这段代码发现，如果在一个排序数组中，有三个数字加起来等于一个给定的和，但我不知道如何计算它的时间复杂度。会喜欢你的意见和想法，如何改善它以及。
注意到，for循环可以在循环中重置自己。
/* function to find if there are 3 values in the
sorted array that sum up to a given sum */
int IsSumOf3( int arr[], size_t size, int sum)
{
int right, left, third;
right = size-1;
left = 0;
while(a
浏览 0提问于2019-02-06得票数 0
2回答
我在C二进制搜索代码中做错了什么？
c、arrays、algorithm、binary-search、function-definition
我正在研究一种二进制搜索算法，为我的编码面试做准备，然而，我的算法只适用于最好的情况，即当搜索的数据位于中点O(1)时。当我将值更改为更糟糕的情况时，光标被卡住了，比如第一个位置。 我知道二分查找的最坏情况是O(log )，所以它应该不会花很长时间。我做错了吗？ #include <stdio.h>
int binary_search(int arr[], int left, int right, int data){
// condition that runs only if true
while(left <= right){
int
浏览 43提问于2020-06-16得票数 0
回答已采纳
2回答
创建BBST的策略，当我们知道大多数插入是正确的？
algorithm、sorting、data-structures、binary-search-tree
我有一个情况，我需要一个平衡的二叉树搜索。我使用了AVL树，但它需要大量的旋转，以创造平衡的高度，同时插入。我已经注意到，大多数投入已经有条不紊。如:8 9 10 11 12 13 2 14 15 16 17 4 18 19 20等当我们知道大多数输入已经就绪时，是否有更好的创建BBST的策略？
浏览 0提问于2014-02-17得票数 2
回答已采纳
1回答
难以理解构建分段树的递归
c#、segment-tree
假设有一个包含n = 5的数组
int [] arr = {1,2,3,4,5};
和
int [] segmentTree = new int[n*4];
以下是构建此segmentTree的代码
buildSegmentTree(a , 1 , 0 , n-1);
void buildSegmentTree(int [] a , int vertex , int leftLimit , int rightLimit)
{
if(leftLimit == rightLimit)
segmentTree[vertex] = a[leftLimit];
e
浏览 6提问于2019-10-14得票数 0
2回答
做QuickSort是为了好玩，但有件事我不明白
python、quicksort
只是想确保这是而不是的家庭作业问题。我这样做只是为了一些乐趣，可能是为了博客。
我正在按照这个实现快速排序的‘就地’版本。
下面是我编写的代码：
# solution 2
def swap(arr, left, right):
try:
tmp = arr[left]
arr[left] = arr[right]
arr[right] = tmp
except IndexError:
print "!IndexError: left, right", left, right
rai
浏览 6提问于2011-06-17得票数 2
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
即时通信 IM
对象存储活动推荐
腾讯云开发者
