二维 ArrayList 二进制搜索 c#

Question

被要求为通过字符串排序的二维数组创建二进制搜索方法。我正在做一个有很多细节的课程的一部分，我不能使用任何预建的搜索方法，但我必须在没有任何学习内容的情况下创建它，我所提供的只是一个标准的二进制搜索方法一个包含整数的一维数组，所以帮助不大。

        private void BtnSearch_Click(object sender, EventArgs e)
        {

            int startIndex = 0;
            int finalIndex = gameArray.Length -1;

            bool flag2 = false;
            string searchTerm = txtSearch.Text;
            int foundIndex = -1;


            while (!flag2 && !((finalIndex - startIndex) <= 1))
            {
                int middle = (finalIndex + startIndex) / 2;
                if (string.Compare(gameArray[middle, 0], searchTerm, true) == 0)
                {
                    foundIndex = middle;
                    flag2 = true;
                    break;
                }
                else
                {
                    if (string.Compare(gameArray[middle, 0], searchTerm, true) > 0)
                        finalIndex = middle;
                    else
                        startIndex = middle;
                }

            }
            if (flag2)
                lstGames.SelectedIndex = foundIndex;
            else
                MessageBox.Show("Not Found");

        }

每次在程序中执行搜索时，我都会不断收到此错误消息。

System.IndexOutOfRangeException: 'Index was outside the bounds of the array.'

在 While 循环执行时发生

真的不太确定我现在做错了什么。

Answer 1

您应该在测试前检查 "middle" 是否等于或大于数组的长度。

当您有 (finalIndex-startIndex> 1) 时，避免使用 !((finalIndex-startIndex)<=1)。太干净了

!flag2 在 while 子句中是不必要的，因为只有在 flag2 为真后才会中断；

编辑：您没有解决索引偏移问题。看看这个BS基本循环

int minIndex=0;
int maxIndex=data.Length-1;

while (minIndex <=maxIndex) { //this is the only control you have to do
  int mid = (minIndex + maxIndex) / 2;
  if (key == data[mid]) { //compare, or do stuff
     return ++mid;
  } else if (key < data[mid]) { //compare or do stuff
     maxIndex = mid - 1; //this -1 is important in performance
  }else {
     minIndex = mid + 1; //this +1 is important in performance
  }
}

而且我建议您遵循 SRP（单一职责 bla bla）。使 "BinarySearch" 成为一个独立的方法，并使其成为 return 找到的索引或 -1 如果未找到，并在需要的地方使用该方法。你甚至可以让它变得通用。

二维 ArrayList 二进制搜索 c#

2D ArrayList Binary Search c#

c#

windows-forms-designer