mappleleaf Ответов: 1

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

Привет

Следуя следующему видео на youtube, я пытаюсь использовать данный алгоритм, чтобы проследить, сколько раз 5 появляется в этом массиве

[1][1][3][3][5][5][5][5][5][9][9][11]


алгоритм таков

findCount(a, n, x, searchfirst){

low = 0;
high = n-1;
result = -1;

while (low <= high){

mid = (low+high)/2;

    if(a[mid] ==x){
     result = mid;

    if(searchfirst){
     high = mid-1;

    }else{
      low = mid+1;

    }


    }

    else if (x < a[mid]) high = mid -1;
    else low = mid +1;
  }

return result


}


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

Вот оригинальное видео:
Подсчет вхождений числа в отсортированном массиве с дубликатами с помощью двоичного поиска - YouTube[^]

Что я уже пробовал:

Когда я прослеживаю его, я получаю

low    high    mid  a[mid] result
    0        11    5    5       5
    0        4     2    3
    3        4     3    3
    4        4     4    5       4
    4        3


вот где я застрял, моя последняя середина находится в индексе 4 (это самый низкий индекс встречаемости из 5)
Я должен меняться от высокой к середине -1 значит 4-1 = 3; низкий-4 Высокий 3 но пока говорит (низкий &ЛТ;=высокий) 4&ЛТ;3 ложь, поэтому я не могу вводить этот цикл while, чтобы взглянуть на высшую встречаемость 5 с другой{низкий = СЧ+1;}. Где я ошибся в копировании этого алгоритма?

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

1 Ответов

Рейтинг:
0

Patrice T

Научитесь правильно делать отступы в вашем коде, это покажет его структуру, и это поможет чтению и пониманию.

findCount(a, n, x, searchfirst){

  low = 0;
  high = n-1;
  result = -1;

  while (low <= high){
    mid = (low+high)/2;
    if(a[mid] ==x){
      result = mid;
      if(searchfirst){
        high = mid-1;
      }else{
        low = mid+1;
      }
    }
    else if (x < a[mid])
      high = mid -1;
    else
      low = mid +1;
  }
  return result
}

Профессиональные редакторы программистов имеют эту функцию и другие, такие как сопоставление скобок и подсветка синтаксиса.
Блокнот++ Главная Страница[^]
личные[^]
[Обновление]
Цитата:
Я не понимаю цели searchfirst


Существует инструмент, который позволяет вам видеть, что делает ваш код, его имя отладчик Это также отличный инструмент обучения, потому что он показывает вам реальность, и вы можете увидеть, какие ожидания соответствуют реальности.
Когда вы не понимаете, что делает ваш код или почему он делает то, что он делает, ответ таков: отладчик.
Используйте отладчик, чтобы увидеть, что делает ваш код. Просто установите точку останова и посмотрите, как работает ваш код, отладчик позволит вам выполнять строки 1 на 1 и проверять переменные по мере их выполнения.

Отладчик - Википедия, свободная энциклопедия[^]
Отладчик здесь, чтобы показать вам, что делает ваш код, и ваша задача-сравнить с тем, что он должен делать.
В отладчике нет никакой магии, он не находит ошибок, он просто помогает вам. Когда код не делает того, что ожидается, вы близки к ошибке.

mappleleaf

Спасибо за отступ моего кода, но я все еще не уверен, как его отследить, чтобы получить общее число вхождений 5, и я не понимаю цели searchfirst