binary-search 相关问题

二进制搜索是用于在排序数组中查找元素的有效算法。基本思想是在每一步中将搜索空间减半。算法的复杂性为O(log(n))。

如何解决此二分搜索代码中 int 的问题

a = [1,2,2,1] b = [2,2] 如果 len(a) > len(b): 我的列表=一个 目标=b 别的: 我的列表 = b 目标=a 答案=[] 分钟 = 0 最大值 = len(my_list) -1 对于目标中的我:#2 同时分钟 <= m...

回答 1 投票 0

为什么mysql在`IN`子句中使用二分查找而不是哈希查找?

您好,我可以看到《高性能 MySQL - O'Reilly》一书指出 MySQL IN 子句使用二分搜索。 例如: 从用户中选择名称 WHERE city_id IN (2, 1, 6, 4, 3, …, 100 我们有 100 个城市...

回答 1 投票 0

为什么我的代码(从 csv 文件排序和搜索)没有显示数据的所有结果?

我创建一个包含类似内容的程序 你想让我做什么? 1. 显示数据 2. 搜索数据 3. 数据排序 4.导出数据 5.退出 我已经创建了从选项 1 到选项的代码...

回答 1 投票 0

如何求一棵有n个节点的AVL树的最大高度?

我的练习考试中有一个问题如下: 给定一个有 23 个节点的二叉搜索树,如果它也具有 AVL 属性,那么该二叉搜索树的最大高度是多少...

回答 1 投票 0

二分搜索左右索引以查找两个排序数组的中位数

给定两个排序数组 A 和 B,其大小分别为 l 和 m。我们的任务是找到这两个排序数组组合的中位数。假设组合数组的长度为 n 即 n = l + ...

回答 1 投票 0

从三个不同的排序数组中找到三个最接近的元素(两个解决方案之间的差异)

//解决方案1 void findClosest(int A[], int B[], int C[], int p, int q, int r) { int 差异 = INT_MAX; // 初始化最小差异 // 初始化结果 int res_i = 0, res_j = 0, res_k = 0; ...

回答 1 投票 0

需要帮助将“查找两个排序数组中的第 k 个最小的”转换为“第 k 个最大的”

我有一些 C++ 代码,可以在 O(log(m * n)) 时间内找到两个排序数组的第 k 个最小项。我知道这不是最佳解决方案,并且我知道可以在 O(log(min(m, n))),

回答 1 投票 0

当二分查找找不到输入值时

def binary_search(arr, 目标): 低,高 = 0,len(arr) - 1 虽然低<= high: mid = (low + high) // 2 print(f"current range: {low+1}부터 {high+1}") pri...

回答 1 投票 0

无分支二分搜索

我很好奇是否有人可以向我解释无分支二分搜索的实现。我在最近的一个问题中看到它提到,但我无法想象它将如何实施。我想这可能是...

回答 2 投票 0

二分查找功能,接受不同类型的数组

我想编写一个二分搜索函数,它将指向数组的指针作为输入并找到可搜索元素的索引。 uint8_t binary_search(uint8_t * 数组,uint8_t 元素); 但是

回答 1 投票 0

使用二叉搜索树的 C 语言简单数据库

我的任务是用 C 语言编写一个简单的数据库。该程序将接收标准输入中的指令并打印它们的结果。说明的格式如下: : 我的任务是用 C 语言编写一个简单的数据库。该程序将接收标准输入中的指令并打印其结果。说明的格式如下:<operation>: <year> <month> <day> <name>。有 3 个操作:“S”(搜索)、“F”(查找)和“D”(删除)。存储指令会将条目存储在数据库中,如果条目已在数据库中,则打印“已存储”或“已存储”。如果该条目在数据库中,查找指令将打印“找到”,否则将打印“未找到”。删除指令将从数据库中删除该条目,如果找到该条目,则打印“已删除”,否则将打印“未找到”。 由于时间限制,我不能简单地使用链表作为我的解决方案。首先,我尝试使用哈希映射(pastebin 链接)。我尝试使用二叉搜索树,但对条目进行哈希处理(pastebin链接)。这些尝试都没有成功(他们通过了简单的测试,但在大型测试中失败了)。最后我只是尝试了“最简单”的方法 - 存储整个条目的二叉树。这次尝试也通过了简单的测试,但在大型测试中失败了......现在我完全陷入困境。这是我当前的代码: #ifdef __STDC_LIB_EXT1__ #define __STDC_WANT_LIB_EXT1__ 1 #define scanf scanf_s // Bit hacky ngl. #endif #include <stddef.h> // NULL #include <stdio.h> // scanf()/scanf_s(), puts() #include <stdlib.h> // malloc(), free() #include <string.h> // strcmp() typedef struct { unsigned short year; unsigned char month, day; char *name; } User; typedef struct BinaryTreeNode { struct BinaryTreeNode *left, *right; User user; } BinaryTree; static inline BinaryTree *BinaryTree_alloc(User user) { BinaryTree *tree = (BinaryTree *) malloc(sizeof(BinaryTree)); tree->left = NULL; tree->right = NULL; tree->user = user; return tree; } static inline void BinaryTree_dealloc(BinaryTree *tree) { if (tree) { BinaryTree_dealloc(tree->left); BinaryTree_dealloc(tree->right); free(tree); } } int BinaryTree_compare(BinaryTree *tree, User user) { if (tree->user.year > user.year) return 1; else if (tree->user.year < user.year) return -1; else if (tree->user.month > user.month) return 1; else if (tree->user.month < user.month) return -1; else if (tree->user.day > user.day) return 1; else if (tree->user.day < user.day) return -1; else return strcmp(tree->user.name, user.name); } BinaryTree *BinaryTree_store(BinaryTree *tree, User user) { if (tree) { switch (BinaryTree_compare(tree, user)) { case 1: tree->left = BinaryTree_store(tree->left, user); break; case -1: tree->right = BinaryTree_store(tree->right, user); break; default: puts("Already stored"); } return tree; } puts("Stored"); return BinaryTree_alloc(user); } BinaryTree *BinaryTree_find(BinaryTree *tree, User user) { if (tree) switch (BinaryTree_compare(tree, user)) { case 1: return BinaryTree_find(tree->left, user); case -1: return BinaryTree_find(tree->right, user); default: puts("Found"); } else puts("Not found"); return tree; } static inline User BinaryTree_find_min_user(BinaryTree *tree) { while (tree->left) tree = tree->left; return tree->user; } BinaryTree *BinaryTree_delete(BinaryTree *tree, User user) { if (tree) switch (BinaryTree_compare(tree, user)) { case 1: tree->left = BinaryTree_delete(tree->left, user); break; case -1: tree->right = BinaryTree_delete(tree->right, user); break; default: if (!tree->left && !tree->right) { free(tree->user.name); free(tree); tree = NULL; puts("Deleted"); } else if (!tree->left || !tree->right) { BinaryTree *root = tree; if (!tree->left) tree = tree->left; if (!tree->right) tree = tree->right; free(root->user.name); free(root); puts("Deleted"); } else { User min_user = BinaryTree_find_min_user(tree->right); tree->user = min_user; tree->right = BinaryTree_delete(tree->right, min_user); } } else puts("Not found"); return tree; } int main() { char operation; User user; BinaryTree *tree = BinaryTree_alloc((User) { 0, 0, 0, NULL }); while (5 == scanf(" %c : %hu %hhu %hhu %m[^\n]", &operation, &user.year, &user.month, &user.day, &user.name)) { switch (operation) { case 'S': BinaryTree_store (tree, user); break; case 'F': BinaryTree_find (tree, user); break; case 'D': BinaryTree_delete(tree, user); break; } } BinaryTree_dealloc(tree); } 有人请帮助我:3 我不确定问题是什么,但您提到“大型”测试失败,因此在递归函数上从传递 User 切换到 User * 将使用更少的堆栈空间。 (不固定)C 不保证尾部调用优化,因此您应该更喜欢迭代而不是递归算法,后者本质上具有未绑定的堆栈大小要求。 如果您先处理特殊情况,那么通常很长的正常情况的缩进就会较少。这也是您通常期望的递归函数(首先是基本情况)。 BinaryTree_compare() 很奇怪,因为您正在比较两个用户,因此将其更改为 User_compare() 并传入两个 User *。调用者假定函数返回 -1、0 或 1,但 strcmp() 的情况并非如此,因此请确保现在确实如此。在通话中,我还切换了参数,因为对我来说,-1 表示树的 left 侧和 +1 右侧更有意义。 (未修复)考虑重构 BinaryTree_find() 和/或 BinaryTree_store() 以消除非常相似的代码。 main() 分配一个空节点,但我认为仅仅盯着 NULL 更有意义。 我删除了inline,因为编译器可能比你更了解它是否使用它。我可能会删除 BinaryTree_find_min_user() 并只在 BinaryTree_delete() 中添加那句台词。 #ifdef __STDC_LIB_EXT1__ #define __STDC_WANT_LIB_EXT1__ 1 #define scanf scanf_s // Bit hacky ngl. #endif #include <stddef.h> // NULL #include <stdio.h> // scanf()/scanf_s(), puts() #include <stdlib.h> // malloc(), free() #include <string.h> // strcmp() typedef struct { unsigned short year; unsigned char month, day; char *name; } User; typedef struct BinaryTreeNode { struct BinaryTreeNode *left, *right; User user; } BinaryTree; static BinaryTree *BinaryTree_alloc(const User *user) { BinaryTree *tree = malloc(sizeof *tree); tree->left = NULL; tree->right = NULL; tree->user = *user; return tree; } static void BinaryTree_dealloc(BinaryTree *tree) { if (!tree) return; BinaryTree_dealloc(tree->left); BinaryTree_dealloc(tree->right); free(tree); } int User_compare(const User *a, const User *b) { if (a->year > b->year) return 1; else if (a->year < b->year) return -1; else if (a->month > b->month) return 1; else if (a->month < b->month) return -1; else if (a->day > b->day) return 1; else if (a->day < b->day) return -1; int rv = strcmp(a->name, b->name); return rv < 0 ? -1 : rv > 0 ? 1 : 0; } BinaryTree *BinaryTree_store(BinaryTree *tree, const User *user) { if (!tree) { puts("Stored"); return BinaryTree_alloc(user); } switch (User_compare(user, &tree->user)) { case -1: tree->left = BinaryTree_store(tree->left, user); break; case 1: tree->right = BinaryTree_store(tree->right, user); break; default: puts("Already stored"); } return tree; } BinaryTree *BinaryTree_find(BinaryTree *tree, const User *user) { if (!tree) { puts("Not found"); return NULL; } switch (User_compare(user, &tree->user)) { case -1: return BinaryTree_find(tree->left, user); case 1: return BinaryTree_find(tree->right, user); default: puts("Found"); } return tree; } static User *BinaryTree_find_min_user(BinaryTree *tree) { for (; tree->left; tree = tree->left); return &tree->user; } BinaryTree *BinaryTree_delete(BinaryTree *tree, User *user) { if (!tree) { puts("Not found"); return tree; } switch (User_compare(user, &tree->user)) { case -1: tree->right = BinaryTree_delete(tree->right, user); break; case 1: tree->left = BinaryTree_delete(tree->left, user); break; default: if (!tree->left && !tree->right) { free(tree->user.name); free(tree); tree = NULL; puts("Deleted"); } else if (!tree->left || !tree->right) { BinaryTree *root = tree; if (!tree->left) tree = tree->left; if (!tree->right) tree = tree->right; free(root->user.name); free(root); puts("Deleted"); } else { User *min_user = BinaryTree_find_min_user(tree->right); tree->user = *min_user; tree->right = BinaryTree_delete(tree->right, min_user); } } return tree; } int main() { char operation; User *user = &(User) {0}; BinaryTree *tree = NULL; while (5 == scanf(" %c : %hu %hhu %hhu %m[^\n]", &operation, &user->year, &user->month, &user->day, &user->name)) { switch (operation) { case 'S': tree = BinaryTree_store (tree, user); break; case 'F': BinaryTree_find (tree, user); break; case 'D': BinaryTree_delete(tree, user); break; } } BinaryTree_dealloc(tree); } 和示例运行: $ cat input.txt S : 2023 11 28 m S : 2023 11 28 m S : 2023 11 28 a S : 2023 11 28 z F : 2023 11 28 m D : 2023 11 28 m F : 2023 11 28 m $ ./a.out < input.txt Stored Already stored Stored Stored Found Deleted Not found

回答 1 投票 0

二分查找给出错误的返回值

我尝试谷歌搜索解决方案,我认为所有解决方案都与我编写的代码相同,但它似乎不起作用。我错过了什么吗? #包括 使用命名空间 std; 整数

回答 1 投票 0

二分搜索方法并不适用于所有情况

我正在尝试做一道 LeetCode 题: 给定一个按升序排序的整数数组 nums 和一个整数目标,编写一个函数在 nums 中搜索目标。如果目标存在,则 r...

回答 1 投票 0

在二分查找中混淆何时使用左< right ; left <= right ; and few more

我很难理解何时使用: 同时(左< right ) { } vs when to use: while (left <= right ) { } Also while setting left and right boundaries sometimes we use: left...

回答 3 投票 0

JavaScript 中比较字符串的最佳方法? [重复]

我正在尝试优化一个在 JavaScript 中对字符串进行二分搜索的函数。 二分查找要求你知道键是 == 主元还是 < the pivot. But this requires two s...

回答 3 投票 0

使用 char 类型的二叉搜索树

我理解整数上的二叉搜索树,因为我知道左子节点必须小于节点,右子节点必须大于节点,当涉及到“char”或“string”类型时,它的t。 ..

回答 2 投票 0

使用二分查找解决分数背包问题

分数背包问题围绕着从给定的集合中选择物品以适合容量有限的背包。每个项目都有一个重量和与其相关的值,目标是

回答 1 投票 0

关于二分查找基础知识的一些疑问

公开课示例{ 公共静态无效主(字符串[] args){ int[] 数字 = {2, 2, 4, 6, 8, 12, 14, 15}; 整数目标= 12; int ans = 搜索(nums, 目标); 系统.out.

回答 2 投票 0

在Python中使用修改后的二分搜索算法查找“交叉”索引

任务是找到两个数组的“交叉”索引。交叉索引是数组 x 和 y 的索引: 断言(x[左] > y[左]) 断言(x[右] < y[right]) I am supposed to...

回答 2 投票 0

为什么 std::upper_bound() 具有线性复杂度?

我正在阅读 USACO Silver 上关于排序集的指南,我遇到了这个警告(s 是一个 std::set 整数): 警告! 假设我们将 s.upper_bound(7) 替换为 upper_bound(...

回答 2 投票 0

© www.soinside.com 2019 - 2024. All rights reserved.