需要理解BinarySearch和IndexOf方法的行为

本文关键字：方法 IndexOf BinarySearch | 更新日期: 2023-09-27 18:07:37

我有一个List，它的值是("Brandenburg"，"Alabama"answers"Alberta")。当我使用BinarySearch("Brandenburg")方法时，它返回-4而不是0。但是我可以得到正确的索引，当排序这个列表的时候。为什么它返回错误的值，如果我使用无序列表?我也从IndexOf("Brandenburg")方法中得到了正确的指标。哪一个方法是有用的，我可以使用?

提前感谢Prithivi

需要理解BinarySearch和IndexOf方法的行为

必须排序，才能使用二分查找。你得到-4的原因是;

你的集合没有排序，对于二进制搜索，列表将在每次迭代中"切"成两半。所以:

开始时，topIndex == 0, bottom = 2

TopIndex ->    (0) "Brandenburg",
               (1) "Alabama" 
BottomIndex -> (2) "Alberta

binarysearch将检查中间的项:(2-0)/2 = 1。如果您正在搜索Brandenburg。它将比较Alabama与您的搜索项。字母B比字母A"大"。因此它将topIndex移动到索引1 

               (0) "Brandenburg",
TopIndex ->    (1) "Alabama" 
BottomIndex -> (2) "Alberta

然后它将与下一个"中间"项进行比较。这里还是Alabama。(2-1) / 2 = 1。它也将与底部索引进行比较，但这是最后一个。

当binarysearch返回一个负数时，表示无法找到该项。负数是应该插入的索引。 (-result -1)所以如果你想添加新的项目，它应该插入索引(--4 -1) == 3

让我解释一下二进制搜索是如何工作的。

假设你有这样一个数组:

{1, 3, 5, 7, 10, 15, 20}

我想求出15的索引。二分查找要做的是查找数组的中间，7。7比15大还是小?如果小于15，对数组的后半部分(10,15,20)再次执行相同的操作。如果大于15，则在前一半(1,3,5)上进行。如果等于15，则意味着找到了15。

这意味着数组必须经过排序才能进行二分查找。这就解释了为什么对数组进行二进制搜索会返回一个负数。因为很明显，该方法无法使用二进制搜索算法找到您请求的字符串。

使用IndexOf可以得到正确的索引。这是因为IndexOf使用线性搜索来查找项目。它会查看数组中的每个元素，并与你找到的元素进行比较。因此，数组是否排序并不重要。

注:我没有读过IndexOf的源代码。如果它发现数组已排序，则可能使用二分搜索。这只是我的猜测。

相关文章：