проблема с алгоритмом двоичного поиска - PullRequest
Новая
       4

проблема с алгоритмом двоичного поиска

0 голосов
/ 25 декабря 2010

приведенный ниже код относится к алгоритму двоичного поиска, пользователь вводит числа в textbox1 и вводит номер, который он хочет перебрать с двоичным поиском в textbox2.У меня с этим проблема, то есть, когда я, например, ввожу 15,21 в textbox1и введите 15 в textbox2 и поместите brakpoint в строку, которую я прокомментировал ниже, и я понял, что она не помещает число в textbox2 в поисковики (с комментариями), для более подробного объяснения я комментирую в code.thanks заранее 

 public void button1_Click(object sender, EventArgs e)
    {


        int searchnums = Convert.ToInt32(textBox2.Text);//the problem is here,the value in textbox2 doesnt exist in searchnums and it has value 0. 

        int result = binarysearch(searchnums);
        MessageBox.Show(result.ToString());
    }
    public int binarysearch(int searchnum)
    {
        string[] source = textBox1.Text.Split(',');
        int[] nums = new int[source.Length];
        for (int i = 0; i < source.Length; i++)
        {
            nums[i] = Convert.ToInt32(source[i]);
        }

        int first =0;

        int last = nums.Length-1;


        while (1<= nums.Length)
        {
        int mid = (int)Math.Floor(first+last / 2.0);
             if (first > last)
            {
                break;
            }
            if (searchnum < nums[mid])
            {
                last = mid - 1;
            }
            if (searchnum > nums[mid])
            {
                first = mid + 1;
            }
            else
            {
                return nums[mid];

            }
        }
        return -1; 


    }

Ответы [ 3 ]

2 голосов
/ 25 декабря 2010

Во-первых, когда вы знаете, что можете разместить точку останова на строке, вы точно знаете, что можете пройти программу целом и посмотреть, какие значения есть в каждой переменной или свойстве. Итак, продолжайте и отлаживайте. Среди прочего, вам, вероятно, не хватает проверки ввода данных в вашей программе.

Во-вторых, в вашей реализации двоичного поиска отсутствует mid пересчет после обновления first или last и условия остановки в случае, если искомый номер не найден в массиве. Вы должны разорвать цикл в случае first == last, независимо от того, соответствует nums[mid] или нет - никто не сказал, что число из textbox2 должно быть в массиве.

2 голосов
/ 25 декабря 2010

Какое это имеет отношение к бинарному поиску? Кажется, проблема в том, что вы не можете прочитать число из текстового поля. Вы уверены, что это правильное текстовое поле? Что это за текст? Кроме того, если вы установите точку останова на строку, которая присваивает значение поисковым системам, она будет равна 0, поскольку она еще не была назначена, установите точку останова на строку ПОСЛЕ.

1 голос
/ 25 декабря 2010

Хорошо, во-первых, я надеюсь, что вы знаете, что двоичный поиск не будет работать, если nums не отсортирован.

Тем не менее, в алгоритме есть несколько проблем. Прежде всего, вы не меняете ни один из ключевых элементов в цикле. Вы изменяете только first и last в цикле, и они там даже не используются, поэтому состояние цикла не меняется.

Так что, я думаю, вы хотели иметь эту строку в начале цикла: 

mid = (first +last)/2;

Кроме того, вам нужно проверить очень вероятное событие, что число не существует. что означает добавление этого в начале цикла к: 

if (last < first) break;

Что, конечно, означает, что первая точка блока массива прошла последнюю точку, что означает, что размер блока является отрицательным. first == last может быть допустимым, когда вы доберетесь до последней ячейки в массиве.

И последний пункт - начать last как размер-1: 

int last = nums.Length - 1;

В конце концов, мы говорим об индексах массивов.

...