二分搜索没有 return 正确的索引

Question

我想在数组中搜索给定整数的索引。如果给定数组中的数字不重复，则代码会执行其工作，例如，如果我们正在 int [] array = new int [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 中搜索整数 2 的索引，但如果给定数组是 int [] array = new int [1, 2, 2, 4, 5, 6, 7, 8, 9, 10, 11]，代码将 return 索引 2，而不是 1。

public static int Bisection(int[] array, int element)
{
    int left = 0;
    int right = array.Length - 1;
    int middle = (left + right) / 2;

    while (array[middle] != element)
    {
        if (array[middle] < element)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
        middle = (left + right) / 2;


        if (right < left)
        {
            return -1;
        }
    }
    return middle;
}

所以我的问题是，如果数组中有多个相同的整数，我应该如何return整数的最低索引？

Answer 1

你可以用 LINQ 解决这个问题。以下代码在 array 中搜索与 element 匹配的第一个数字 returns 它是 array 中的索引：

int[] array = { 1, 2, 2, 4, 5, 6, 7, 8, 9, 10, 11 };
int element = 2;
var result = Enumerable.Range(0, array.Length).FirstOrDefault(i => array[i]==element);

如果您想要 array 中与 element 匹配的所有数字的索引：

var result = Enumerable.Range(0, array.Length).Where(i => array[i]==element).ToArray();

Answer 2

检查这个：

public static int Bisection(int[] array, int element)
{
    int left = 0;
    int right = array.Length - 1;
    int middle = (left + right) / 2;

    while (array[middle] != element || (middle > 0 && array[middle - 1] == element))
    {
        if (array[middle] < element)
        {
            left = middle + 1;
        }
        else
        {
            right = middle - 1;
        }
        middle = (left + right) / 2;


        if (right < left)
        {
            return -1;
        }
    }
    return middle;
}

while条件已更改。

二分搜索没有 return 正确的索引

Bisection search doesnt return the correct index

c#

arrays

bisection