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 that you have read and understand our privacy policy and code of conduct.

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