使用二进制搜索对未列出的数组进行排序？
Sorting through unlisted array using binary search?
如果我有一个未排序的数组，并且我需要在不切换它们的情况下找到某个元素，我通常会使用线性搜索。但是，如果我决定使用快速排序或归并排序对整个数组进行排序，然后使用二进制搜索找到我想要查找的元素，之后我将重新排列数组，使其恢复到开始时的样子。它的时间复杂度和 space 复杂度是多少？对于更大的数据集，它会比线性搜索更有效吗？
不，那对提高时间复杂度没有帮助。瓶颈是排序（没有任何可用的数据假设）具有 O(nlogn) 时间复杂度，这比进行线性搜索时获得的线性时间复杂度更差通过未排序的数组。
即使您拥有适合基数排序的数据类型，并获得具有线性时间复杂度的排序数组，这仍然不会改善您已经通过简单搜索获得的时间复杂度。
在没有任何额外信息的情况下，您无法比线性时间复杂度做得更好。当您意识到数组中的 any 槽可以容纳您要查找的元素时，您就可以轻松掌握这一点。因此，在最坏的情况下，这将是您查看数组中所有其他 n-1 插槽之后查看的最后一个插槽。因此，您执行了 n 个操作，这表示线性时间复杂度。
正如您还询问了 space 复杂性：排序可以就地完成，因此如果您仍然决定对数据进行排序，则不会对 space 复杂性产生影响。
如果每次需要查找时都进行排序然后搜索，则整个操作需要 O(nlogn)，这比线性搜索的 O(n) 更糟糕。
OTOH，如果列表的内容从不改变（或很少改变），您可以在开头保留一个排序的副本，然后 运行 在该副本上进行所有搜索。
如果您将列表实现为排序数据结构（通常是 binary search tree），您可以实现 O(logn) 搜索更改列表，尽管您是列表操作，例如添加和删除到该列表也变为 O(logn)。 Java 的 TreeSet/TreeMap 使用那个。
如果我有一个未排序的数组，并且我需要在不切换它们的情况下找到某个元素，我通常会使用线性搜索。但是，如果我决定使用快速排序或归并排序对整个数组进行排序，然后使用二进制搜索找到我想要查找的元素，之后我将重新排列数组，使其恢复到开始时的样子。它的时间复杂度和 space 复杂度是多少？对于更大的数据集，它会比线性搜索更有效吗？
不，那对提高时间复杂度没有帮助。瓶颈是排序（没有任何可用的数据假设）具有 O(nlogn) 时间复杂度，这比进行线性搜索时获得的线性时间复杂度更差通过未排序的数组。
即使您拥有适合基数排序的数据类型，并获得具有线性时间复杂度的排序数组，这仍然不会改善您已经通过简单搜索获得的时间复杂度。
在没有任何额外信息的情况下，您无法比线性时间复杂度做得更好。当您意识到数组中的 any 槽可以容纳您要查找的元素时，您就可以轻松掌握这一点。因此，在最坏的情况下，这将是您查看数组中所有其他 n-1 插槽之后查看的最后一个插槽。因此，您执行了 n 个操作，这表示线性时间复杂度。
正如您还询问了 space 复杂性：排序可以就地完成，因此如果您仍然决定对数据进行排序，则不会对 space 复杂性产生影响。
如果每次需要查找时都进行排序然后搜索，则整个操作需要 O(nlogn)，这比线性搜索的 O(n) 更糟糕。
OTOH，如果列表的内容从不改变（或很少改变），您可以在开头保留一个排序的副本，然后 运行 在该副本上进行所有搜索。
如果您将列表实现为排序数据结构（通常是 binary search tree），您可以实现 O(logn) 搜索更改列表，尽管您是列表操作，例如添加和删除到该列表也变为 O(logn)。 Java 的 TreeSet/TreeMap 使用那个。