C#中数组中字符串的二进制搜索

本文关键字:二进制 搜索 字符串 数组 | 更新日期: 2023-09-27 18:25:05

好吧,所以我已经在这个错误上呆了大约18个小时,完全迷失了方向。我试图做的是进行二进制搜索,其中搜索从数组的中间开始,然后每次通过将搜索到的项与中间项进行比较来消除一半的数组。到目前为止,我的代码没有产生错误,除非我试图比较搜索到的术语是否大于中间术语。我知道我正在尝试比较两个字符串,所以大于不适用,但我不知道其他方法

public partial class MainWindow : Window
{
    public MainWindow()
    {
        InitializeComponent();
    }
    string[] contacts = new string[20];
    private void button1_Click(object sender, RoutedEventArgs e)
    {
        listBox1.Items.Clear(); //Clears the ListBox of all previous items
        if (!File.Exists("Week3List.txt")) //Verifies that the file exists
        {
            MessageBox.Show("You need to write the file first", "Validation", MessageBoxButton.OK); //Notifies the user if the file does not exist
            return;
        }
        using (StreamReader sr = new StreamReader("Week3List.txt")) //Designates the path to the file that was created
        {
            try
            {
                contacts = File.ReadAllLines("Week3List.txt");
                Array.Sort(contacts);
                foreach (string contact in contacts)
                {
                    listBox1.Items.Add(contact);
                }
                sr.Close(); //Closes the StreamReader
            }
            catch (Exception ex) //A catch to handle access errors
            {
                MessageBox.Show(ex.ToString(), "Exception Handler", MessageBoxButton.OK); //Adds the error message to the ListBox
            }
        }
    }
    private void button2_Click(object sender, RoutedEventArgs e)
    {
        bSearch(contacts);
    }
    private void bSearch(string[] contacts)
    {
        int index = Array.BinarySearch(contacts, textBox1.Text);
    }
    public int BinarySearch(string[] contacts, string searchTerm)
    {
        int first = 0;
        int last = contacts.Length - 1;
        int position = -1;
        bool found = false;
        int compCount = 0;
        searchTerm = textBox1.Text;
        while (found != true && first <= last)
        {
            int middle = (first + last) / 2;
            if (contacts[middle] == searchTerm)
            {
                found = true;
                position = middle;
                compCount++;
                MessageBox.Show("Your search has been found after " + compCount + "comparisons.");
            }
            else if (contacts[middle] > searchTerm)
            {
                last = middle;
                compCount++;
            }
            else
            {
                first = middle;
                compCount++;
            }
        }
        return position;
        return compCount;
    }
}
}

有人看到我哪里错了吗?或者知道一种方法可以将两者进行比较,以获得更大或更小的值吗?我想,因为它是排序的,它可能会比较第一个字母,并根据它来确定,但我错了。

C#中数组中字符串的二进制搜索

只需使用List<T>.BinarySearch方法。

List<String> myList = new List<String>{"Apple", "Microsoft", "Yahoo", "StackOverflow" };
myList.Sort(); //Apple Microsoft StackOverflow Yahoo 
myList.BinarySearch("Yahoo"); // 3

或者如果使用Array:

string[] myArr = new string[]{"Apple", "Microsoft", "Yahoo", "StackOverflow" };
Array.Sort(myArr); //Apple Microsoft StackOverflow Yahoo 
Array.BinarySearch<string>(myArr, "Yahoo"); // 3

好的,感谢RegularExpression提出的研究字符串比较方法的建议。我更改了代码

if (contacts[middle] == searchTerm)else if (contacts[middle] > searchTerm)

CCD_ 5和CCD_ 6

它现在运行得很好!感谢大家的快速回复。

看看这个比较字符串的方法。它会告诉你一个字符串是大于、小于还是等于另一个字符串:

http://msdn.microsoft.com/en-us/library/zkcaxw5y%28v=vs.110%29.aspx

好吧,你试过了吗:

contacts.ToList().BinarySearch(searchTerm);

如果你想对字符串数组进行二进制搜索,这就是方法。你可能想为StringComparer选择一个不同的区域性。

string[] arr = {"a","b","c","d","e","f","g"};
int k = Array.BinarySearch(arr,"d",StringComparer.InvariantCulture);

如果您想在不使用内置编程语言的扩展和助手你应该这样做:(见在线演示)

重要提示:您的Array应该是sorted,因为Binarry-Search不在UnSorted列表中工作。

 static int Find(string[] data, string SearachItem)
    {
        //It is mandatory to turn off case-sensitive by convert values to lowercase or uppercase
        ConvertArrayToLower(data); 
        string Lower = SearachItem.ToLower();
        
        //initiate
        char XChar = Lower[0]; // we will compare first char of Search Item by first char of array values
        int FirstIndex = 0;
        int LastIndex = data.Length - 1;
        while (FirstIndex <= LastIndex)
        {
            int MiddelIndex = (FirstIndex + LastIndex) / 2;
            char middel = data[MiddelIndex][0];
            if (XChar > middel)
                FirstIndex = MiddelIndex + 1;
            else if (XChar < middel)
                LastIndex = MiddelIndex - 1;
            else if (data[MiddelIndex] != Lower) // maybe the first char of two or more values will be the same so we should go to the next step
            {
                FirstIndex = MiddelIndex + 1;
            }
            else return MiddelIndex; // if found
        }
        //if not found
        return -1;
    }
    private static void ConvertArrayToLower(string[] data)
    {
        for (int i = 0; i < data.Length; i++)
        {
            data[i] = data[i].ToLower();
        }
    }

查看在线演示