c#-二进制搜索字符串列表 [英] c# - Binary Search String List

问题描述

我目前正在构建一个控制台应用程序，可以搜索和排序不同类型的数据.正如问题所暗示的；我需要为字符串列表制作二进制搜索算法的帮助. 我必须指出，我无法使用内置的c#函数(例如list.binarysearch)，该算法必须从头开始编写.此外，列表包含具有相同字符串值的多个项目，因此我也需要找到所有这些项目.我已经按字母顺序对列表进行了排序，因此我将利用算法来查找要搜索的字符串值的上限和下限.

I'm currently building a console application that can search and sort different types of data. As the question suggests; I need help making a binary search algorithm for a string list. I must point out that I can't make use of the built-in c# functions like list.binarysearch , the algorithm has to be coded from scratch. Also the list contains multiple items of the same string value so I need to find all of these too. I've already sorted the list in alphabetical order so I will make use of algorthims to find the upper and lower-bounds of the string value being search.

首先，我将展示如何格式化列表.

I will start off by showing how I've formatted the list.

var list = new List<Demo>
        {   
            new Demo {Col = "Blue", S1 ="88", S2 ="Yes"},
            new Demo {Col = "Green", S1 ="43", S2 ="Yes"},
            new Demo {Col = "Green", S1 ="216", S2 ="No"},
            new Demo {Col = "Yellow", S1 ="100", S2 ="No"}
        };

该列表已按照'Col'值的字母顺序进行排序.列表实际上比这个要大得多，但是您知道了.二进制搜索需要搜索所有"Col"值并找到特定的字符串值.

The list has been sorted in to alphabetical order of the 'Col' values. The list is actually much larger than this but you get the idea. The binary search needs to search all the 'Col' values and find a particular string value.

下面，我将展示适用于int数组的二进制搜索算法.

Below I will show my binary search algorithm that works on int arrays.

public static int BinarySearch_R(int key, int[] array, int low, int high)
    {
        if (low > high) return -1;
        int mid = (low + high) / 2;
        if (key == array[mid])
        {

            return mid;
        }
        if (key < array[mid]) {
            return BinarySearch_R(key, array, low, mid - 1);
        } else {
            return BinarySearch_R(key, array, mid + 1, high);
        }
    }

我想为上面的列表改编此算法.

I want to adapt this algorithm for my list above.

最后，我将向您展示搜索上限和下限的代码.

Finally I will show you the code for searching the upper and lower bounds.

public static int lower_bound(int key, int[] arr , int low, int high)
    {
        if (low > high)
            //return -1;
            return low;

        int mid = low + ((high - low) >> 1);
        //if (arr[mid] == key) return mid;

        //Attention here, we go left for lower_bound when meeting equal values
        if (arr[mid] >= key) 
            return lower_bound(key, arr, low, mid - 1);
        else
            return lower_bound(key, arr, mid + 1, high);
    }

public static int upper_bound(int key, int[] arr,  int low, int high)
    {
        if (low > high)
            //return -1;
            return low;

        int mid = low + ((high - low) >> 1);
        //if (arr[mid] == key) return mid;

        //Attention here, we go right for upper_bound when meeting equal values
        if (arr[mid] > key) 
            return upper_bound(key, arr, low, mid - 1);
        else
            return upper_bound(key, arr, mid + 1, high);
    }

我知道我已经做了很多工作，即使您只是帮助解决了部分问题，我也会很感激.如果您需要更多信息或代码，请询问.

I know that I've asked for a lot to be done so even if you just help out part of the problem I'll be thankful. If you need any more information or code, just ask.

推荐答案

首先，我要指出的是，您正在将数组传递给函数.那么，为什么要使用该列表?

First of all I would like to point out, you are passing an array into your function. So, why are you using the list?

据我所知，二进制搜索仅在对数组排序时才起作用.因此，我建议您对列表进行事先排序.尽管我什至在排序后都找不到任何解决方案来搜索您的自定义列表(使用二进制搜索).

Again, as far as I know, Binary Search works only when an array is sorted. So, I would suggest, sort your list beforehand. Though I cannot find any solution for searching your custom list(using Binary search) even after sorting.

我希望以上几点对您有所帮助.可能是的，您已经知道他们了.我是StackOverflow的新手，所以请让我知道我的回答是否对您有帮助.

I hope these points will help you. May be, you know them already. I am new at StackOverflow, so, please let me know whether my answer helped you or not.

这篇关于c#-二进制搜索字符串列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！