2

Есть задание: Осуществить поиск указанного (с клавиатуры) элемента в массиве, используя указанный метод поиска). Метод поиска: Бинарный. Ниже, представлен код. Как мне реализовать бинарный поиск в этом коде?

#include <iostream>
#include <ctime>
#include <iomanip>
using namespace std;
void ShakerSort(int *arr, int size)
{
int leftMark = 1;
int rightMark = size - 1;
while (leftMark <= rightMark)
{
    for (int i = rightMark; i >= leftMark; i--)
        if (arr[i - 1] < arr[i])
            swap(arr[i], arr[i - 1]);
    leftMark++;


    for (int i = leftMark; i <= rightMark; i++)
        if (arr[i - 1] < arr[i])
            swap(arr[i], arr[i - 1]);
    rightMark--;

    cout << "\nИтерация: " << leftMark - 1; // просмотр количества итераций
}
}
void ShakerInput()
{
srand(time(NULL));
cout << "Размер массива: ";
int size;
cin >> size;
int *A = new int[size];

for (int k = 0; k < size; k++)
{
    A[k] = rand();
    cout << A[k] << " | ";
}
for (int k = 0; k < size; k++)
{
    cout << A[k] << " | ";
}
ShakerSort(A, size);

cout << "\nМассив после сортировки:\n";
for (int k = 0; k < size; k++)
{
    cout << A[k] << " | ";
}

cout << endl;
}
void insertionSort(int *arrayPtr, int length)
{
int temp,
    item;
for (int counter = 1; counter < length; counter++)
{
    temp = arrayPtr[counter];
    item = counter - 1;
    while (item >= 0 && arrayPtr[item] < temp)
    {
        arrayPtr[item + 1] = arrayPtr[item];
        arrayPtr[item] = temp;
        item--;
    }
}
}
void insertionInput()
{
srand(time(NULL));
setlocale(LC_ALL, "rus");
cout << "Введите размер массива: ";
int size_array;
cin >> size_array;

int *sorted_array = new int[size_array];
for (int counter = 0; counter < size_array; counter++)
{
    sorted_array[counter] = rand();
    cout << setw(2) << sorted_array[counter] << "  ";
}
cout << " | ";

insertionSort(sorted_array, size_array);

for (int counter = 0; counter < size_array; counter++)
{
    cout << setw(2) << sorted_array[counter] << "  ";
}
cout << " | ";

delete[] sorted_array;
}
int main()
{
setlocale(LC_ALL, "rus");
system("color F0");
int input;
while (true)
{
    cout << "\nКакую сортировку предпочитаете? : (1 - Шейкерную, 2 - 
Вставки, 3 - Выход)\n";
    cin >> input;
    switch (input) {
    case 1:
        ShakerInput();
        break;
    case 2:
        insertionInput();
        break;
    case 3:
        return 0;
    default:
        cout << "Повторите ввод!\n";
        break;
    }
}
system("PAUSE");
}
2
  • Не знаете как передавать массив между функциями?
    – JaponDemon
    12 апр 2018 в 19:35
  • К сожалению, нет.
    – Boredix
    12 апр 2018 в 19:41

2 ответа 2

2

Вы можете решить Вашу задачу используя std::lower_bound (он же бинарный поиск) и не рожать велосипед ))

Вот пример использования данного метода: (если у вас Другой тип контейнера, или прикрутите его, или оберните в vector)

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>


template<typename T>
std::size_t BinaryPositinSearch(std::vector<T>& v, T val) {

    if (std::is_sorted(std::begin(v), std::end(v))) {
        auto it = std::lower_bound(std::begin(v), std::end(v), val);
        if (it != std::end(v) && *it == val) {
            return static_cast<std::size_t>(std::distance(std::begin(v), it));
        }
    } else {
        throw std::runtime_error{"Error : container is not sorted"};
    }

    return v.size() + 1;
}


int main()
{
    std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    try {
        auto ret{BinaryPositinSearch(v, 1)};
        if (ret != v.size() + 1) {
            std::cout << "pos : " << ret << std::endl;
        }
    } catch (std::exception& exc) {
            std::cout << exc.what() << std::endl;
    } catch (...) {
        std::cout << "unknown error ~ !"<< std::endl;
    }

    return 0;
}
1

У вас есть две функции сортировки. Нужно инициализировать массив, сортировать, т.е. вызвать ShakerSort(int *arr, int size) или insertionSort(int *arrayPtr, int length) с аргументами имя вашего массива и его размера. Теперь вам нужно искать конкретный элемент в массиве.

Сравниваете со средным элементом массива (index = size/2). Если ваше число больше, то сравниваете со средным элементом первой половины, в обратном случаи со средным элементом второй половины, так пока index > 0 || index == size - 1. Если в этом цикле имело место равенства A[index] с заданным числом, то говорим, что нашли. В обратном случаи нет такого числа в массиве.

Я добавлю к ответу пример таково поиска:

ShakerSort(A,  size);
int k = 0, middle = 0, left = 0, right = size, index = 0;
cout << "введите число";
cin >> k;        
while (left != right)
{
    middle = (left + right) / 2;        
    if (k < A[middle])      
        right = middle - 1;      
    else if (k > A[middle])  
        left = middle + 1;     
    else                     
        index = middle;           
} 
if (index) 
   cout << "число найдено в массиве по индексу _ " << index ;
else
   cout << "Не найдено";

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

1

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.