Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
1 / 1 / 1
Регистрация: 07.09.2014
Сообщений: 88
1

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

17.05.2016, 11:54. Просмотров 1227. Ответов 1
Метки нет (Все метки)


Здравствуйте, у меня есть массив слов words в котором мы будем находить необходимые слова, с помощью массива wordsForFind, слова нужно находить с помощью бинарного поиска, вот что реализовано: сам метод бинарного поиска для слов
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  public static int searchString(String[] names, String key) {
  int first = 0;
    int counter = 0;
    int last  = names.Length;
 
    while (first < last) {
        int mid = (first + last) / 2;
        if (key.CompareTo(names[mid]) < 0) {
            last = mid;
        } else if (key.CompareTo(names[mid]) > 0) {
            first = mid + 1;
        } else {
            return mid;
        }
        counter++;
    }
    return -(first + 1);
 
    
}
и вот как он вызывается:
C#
1
2
3
4
5
6
7
8
9
10
11
12
int results;
            for (int key = 0; key < wordsForFind.Length; key++)
          {
              results = searchString(words, wordsForFind[key]);
          if (results >= 0) {
              Console.WriteLine(wordsForFind[key] + " is at index " + results);
         }
         else {
             Console.WriteLine(wordsForFind[key] + " is not in the array.");
    }
         
}
это просто кусок кода, она работает, но мне нужно завести счётчик который бы искал количество сравнений при поиске, его нужно где то в самом методе , где то в while поместить? (в коде в методе самом видно переменную counter) я так пробовал , но я не знаю правильно ли + мне нужно как то на консоль этот счетчик вывести я пробовал просто в конце метода написать Console.Writeline() но ничего не выводит, так как делаю неправильно , можете плиз направить в нужное русло? Спасибо

Добавлено через 10 часов 13 минут
так в каком месте правильнее написать counter?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
17.05.2016, 11:54
Ответы с готовыми решениями:

Количество сравнений и перестановок в алгоритме слиянием
Привет всем, пробуй найти количество сравнений и перестановок в алгоритме слиянием. Но результат...

Как подсчитать количество итераций в поиске методом дихотомии (бинарного поиска)?
Добрый день. Есть алгоритм поиска методом дихотомии. Как в нём посчитать количество итераций,...

Ошибка в алгоритме бинарного поиска на python 3.7 в sublime text 3
В редакторе sumlime text 3 ввел данный код, и пишет что ошибка в 18 строчке, как я понял 18 и 19...

Подсчитать количество присваиваний и количество сравнений при сортировке
Составить программу, которая для массива, заполненного случайными целыми числами, проводит...

1
Эксперт .NET
14836 / 11224 / 2946
Регистрация: 17.09.2011
Сообщений: 18,794
17.05.2016, 13:59 2
Ну можно так сделать:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
  public static int searchString(String[] names, String key, out int comparisonCount) {
  int first = 0;
    int last  = names.Length;
 
    comparisonCount = 0; 
    while (first < last) {
        int mid = (first + last) / 2;
        int result = key.CompareTo(names[mid]);
        comparisonCount++;
        if (result < 0) {
            last = mid;
        } else if (result > 0) {
            first = mid + 1;
        } else {
            return mid;
        }
    }
    return -(first + 1);
 
}
И передавать его в метод, а потом выводить:
C#
1
2
3
int counter;
results = searchString(words, wordsForFind[key], out counter);
Console.WriteLine(counter);
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.05.2016, 13:59

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Подсчитать количество сравнений исходного и отсортированного массивов
Доброго времени суток. Нужна помощь в подсчете количества сравнений.Вот код uses crt; const N =...

Правильно подсчитать количество перестановок и сравнений в сортировках
Здравствуйте, помогите, пожалуйста, правильно расставить Changes (Перестановки) и Compares...

Подсчитать количество проходов и обменов в алгоритме вставками
Подсчитать количество проходов и обменов в алгоритме вставками , как реализовать в коде, добрые...

Подсчитать количество выполненных сравнений и перестановок в лучшем, худшем и в среднем
помогите пожалуйста


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.