二进制搜索的排序数组

本文介绍了二进制搜索的排序数组的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我试图寻找使用这个二进制搜索code下行的排序的数组。然而，当我对它进行排序，并尝试搜索，它不回来任何结果，只是一个装载图标永远不会消失，如果它有一个无限循环。我不知道是什么问题，因为code看起来合乎逻辑的。

这是ASPX 4.0框架，C＃。在此先感谢！

保护无效Button2_Click（对象发件人，EventArgs的发送）    {        字符串项= TextBox1.Text;        INT目标= Convert.ToInt16（项目）;        INT中旬，第一= 0去年= mynumbers.Length - 1;        //与降值的排序的数组        而（第一＆LT; =上）        {            中期=（第一+最后一个）/ 2;            如果（目标＆LT;通过myNumbers [MID]）                第=月中+ 1;            如果（目标＆GT;通过myNumbers [MID]）                最后=中旬 - 1;            其他                Label11.Text =目标+项目+ +通过myNumbers [MID]在索引中发现;        }

解决方案

有在阵列类二进制搜索：

INT指数= Array.BinarySearch（通过myNumbers，目标）;

有关降序排列，这可以很容易地完成了 ReverseComparer 这是很容易写，如：

公共类ReverseComparer＆LT; T＆GT; ：的IComparer＆LT; T＆GT;    {        公众诠释比较（T X，T Y）        {            返回的Comparer＆LT; T＆GT; .Default.Compare（Y，X）;        }    }

然后：

INT指数= Array.BinarySearch（数字，7，新ReverseComparer＆LT; INT＆GT;（））;

如果这是一个学术活动，你必须使用自定义搜索，当然，这将不适用。如果它有成为一类的自定义算法，那么问题是，当发现你必须跳出循环，而指数在中期，而不是通过myNumbers [MID] ：

//与降值的排序的数组    而（第一＆LT; =上）    {        中期=（第一+最后一个）/ 2;        如果（目标＆LT;通过myNumbers [MID]）        {            第=月中+ 1;        }        如果（目标＆GT;通过myNumbers [MID]）        {            最后=中旬 - 1;        }        其他        {            //该指数中期，而不是​​通过myNumbers [MID]，你需要在这里打破            //一旦发现或者一旦发现它是一个无限循环。            Label11.Text =目标+项目+ +中在索引中发现;            打破;        }    }

而实际上，我可能会设置一个布尔标志，而不是让算法纯洁，不混合与输出担忧的发现，这也将使其更容易知道发生了什么事，如果你退出循环与未找到：

布尔发现= FALSE;    //与降值的排序的数组    而（发现和放大器;！＆放大器;第一＆LT; =上）    {        中期=（第一+最后一个）/ 2;        如果（目标＆LT;通过myNumbers [MID]）        {            第=月中+ 1;        }        如果（目标＆GT;通过myNumbers [MID]）        {            最后=中旬 - 1;        }        其他        {            //你需要在这里停止一旦发现或者一旦发现它是一个无限循环。            发现= TRUE;        }    }    Label11.Text =发现        ？ 项目+项目+被发现的位置+中旬        ：项+项目+未发现;

I am trying to search a descending sorted array using this binary search code. However, after I sort it, and try to search, it doesn't come back with any result, just a loading icon that never goes away as if it has an infinite loop. I'm not sure what the problem is because the code looks logical.

This is aspx with 4.0 framework, c#. Thanks in advance!

protected void Button2_Click(object sender, EventArgs e) { String item = TextBox1.Text; int target = Convert.ToInt16(item); int mid, first = 0, last = mynumbers.Length - 1; //for a sorted array with descending values while (first<=last) { mid = (first + last) / 2; if (target < mynumbers[mid]) first = mid + 1; if (target > mynumbers[mid]) last = mid - 1; else Label11.Text = "Target " + item + " was found at index " + mynumbers[mid]; }

解决方案

There is a binary search in the Array class:

int index = Array.BinarySearch(mynumbers, target);

For descending order, this can be easily accomplished with a ReverseComparer which is easy to write like:

public class ReverseComparer<T> : IComparer<T> { public int Compare(T x, T y) { return Comparer<T>.Default.Compare(y, x); } }

Then:

int index = Array.BinarySearch(numbers, 7, new ReverseComparer<int>());

If this is an academic exercise and you must use a custom search, of course, this won't apply. If it's got to be a custom algorithm for a class, then the problems are that you must break out of the loop when found, and the index is at mid, not at mynumbers[mid]:

//for a sorted array with descending values while (first<=last) { mid = (first + last) / 2; if (target < mynumbers[mid]) { first = mid + 1; } if (target > mynumbers[mid]) { last = mid - 1; } else { // the index is mid, not mynumbers[mid], and you need to break here // once found or it's an infinite loop once it finds it. Label11.Text = "Target " + item + " was found at index " + mid; break; } }

And actually, I'd probably set a bool flag instead to keep the algorithm pure and not mix the find with the output concerns, this will also make it easier to tell what happened if you exit the loop with not found:

bool found = false; //for a sorted array with descending values while (!found && first<=last) { mid = (first + last) / 2; if (target < mynumbers[mid]) { first = mid + 1; } if (target > mynumbers[mid]) { last = mid - 1; } else { // You need to stop here once found or it's an infinite loop once it finds it. found = true; } } Label11.Text = found ? "Item " + item + " was found at position " + mid : "Item " + item + " was not found";