搜索排序数组的最快搜索算法 [英] fastest search algorithm to search sorted array

问题描述

我有一个仅包含值0和1的数组.它们分别存储在数组中.例如，数组的前40％为0，其余60％​​为1.我想找出0和1之间的分割点.我想到的一种算法是二进制搜索.由于性能对我很重要，因此不确定二进制搜索是否可以为我带来最佳性能.分割点是随机分布的.数组以0和1分割后的格式给出.

I have an array which only has values 0 and 1. They are stored separately in the array. For example, the array may have first 40% as 0 and remaining 60% as 1. I want to find out the split point between 0 and 1. One algorithm I have in mind is binary search. Since performance is important for me, not sure if binary search could give me the best performance. The split point is randomly distributed. The array is given in the format of 0s and 1s splitted.

推荐答案

在给数组 时，保持计数的看似聪明的答案并不成立.

The seemingly clever answer of keeping the counts doesn't hold when you are given the array.

计数为O(n)，因此线性搜索也是如此.因此，计数不是最佳方法！

Counting is O(n), and so is linear search. Thus, counting is not optimal!

二进制搜索是您的朋友，并且可以在O(lg n)时间内完成工作，您可能知道这是

Binary search is your friend, and can get things done in O(lg n) time, which as you may know is way better.

当然，如果您仍然必须处理数组(从文件读取，用户输入等)，请利用该时间来计数1s和0s的数量并进行处理(您甚至不必存储任何数据，只需保留计数即可.

Of course, if you have to process the array anyways (reading from a file, user input etc.), make use of that time to just count the number of 1s and 0s and be done with it (you don't even have to store any of it, just keep the counts).

如果要编写点库，则要写一个库，库中有一个名为getFirstOneIndex(sortZeroesOnesArr: Array[Integer]): Integer的函数，该函数接收一个由1和0组成的排序数组，并返回第一个1的位置，因此不计算二进制搜索

To drive the point home, if you are writing a library, which has a function called getFirstOneIndex(sortZeroesOnesArr: Array[Integer]): Integer that takes a sorted array of ones and zeroes and returns the position of the first 1, do not count, binary search.

这篇关于搜索排序数组的最快搜索算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！