§ 19. Бінарны пошук у адсартаваным масіве

Практыкаванні

    

1. Зададзены упарадкаваны масіў (вектар) з цэлых лікаў. Прачытаць даныя з файла. Можна выкарыстаць файл, які быў атрыманы пры рашэнні задач на сартаванне масіву. Выкарыстаць алгарытм бінарнага пошуку і выканаць паказаныя дзеянні.

    1. Атрымаць колькасць элементаў, роўных x. Масіў упарадкаваны ў парадку неспадання.
    2. Выдаліць элемент, роўны x. (Мяркуецца, што такі элемент існуе і з’яўлецца адзіным.) Масіў упарадкаваны ў парадку неспадання.
    3. Уставіць элемент, роўны x, не парушаючы ўпарадкаванасці. (Такі элемент можа быць.) Масіў упарадкаваны ў парадку неўзрастання.
    4. Выдаліць з зыходнага масіву ўсе элементы, якія роўны элементам іншага ўпарадкаванага масіву. Масіў упарадкаваны ў парадку неўзрастання.

2. Зададзены вектар радкоў, элементамі якога з’яўляюцца прозвішчы. Даныя прачытаць з файла. Прозвішчы адсартаваны ў алфавітным парадку. Напісаць праграмы для рашэння задач, выкарыстоўваючы метад бінарнага пошуку.

      1. Вызначыць, колькі чалавек у спісе пасля Іванова. (Мяркуецца, што калі такое прозвішча ёсць, то яно — адзінае ў спісе.)
      2. Вызначыць, колькі ў спісе людзей з прозвішчам Іваноў. (Мяркуецца, што такое прозвішча ёсць у спісе.)
      3. У спіс трэба ўставіць прозвішча, уведзенае з клавіятуры. Вызначыць месца, на якое павінна быць устаўлена гэта прозвішча.
      4.  Аформіць запыт на пошук у спісе прозвішчаў, што пачынаюцца на якую-небудзь літару. У якасці адказу атрымаць усе знойдзеныя прозвішчы і іх нумары.