Question

Дан массив из n элементов и дается число k написать программу которая находит элемент массива равный k и выводит его индекс или -1 если такого элемента нет ВАЖНО: програма должна работать быстрее чем за линейное время то есть просто перебор не пройдет

Answer 1

Ответ:

#include <iostream>

#include <Windows.h>

using namespace std;

 

int main()

{

   SetConsoleCP(1251);

   SetConsoleOutputCP(1251);

   int n;

   cin >> n;//Вводим размер массива

   int *arr = new int[n];

   for (int i = 0; i < n; i++)

   {

       cin >> arr[i];//Вводим числа массива

   }

   int k;

   cin >> k;//Вводим искомое

   int index = 0;

 

   for (int i = 0; i < n; i++)

   {

       if (arr[i] == k)

       {

           index = i;//Запоминаем индекс числа в массиве

           break;//Так как цифры во входных данных две - прерываем цикл при первом же совпадении

       }

   }

   cout << index-1 << endl;

   system("pause");

   return 0;

}

Answer 2

#include <iostream>

using namespace std;

int main() {

   int n,k;

   cin >> n;

   pair<int,int> a[n];

   for(int i = 0; i < n; i++){

       int x;

       cin >> x;

       a[i] = {x,i};

   }

   cin >> k;

   sort(a,a+n);

   int l = 0, r = n-1;

   while(l <= r){

       int mid = (l+r)/2;

       if(a[mid].first == k){

           cout << a[mid].second;

           return 0;

       }

       else if(a[mid].first < k)

           l = mid+1;

       else if(a[mid].first > k)

           r = mid-1;

   }

   cout << -1;

}

Answer 3

Для решения данной задачи можно использовать алгоритм двоичного поиска, который работает быстрее, чем линейный перебор. 1. Создадим функцию `binary_search`, которая будет принимать массив `arr`, число `k`, а также начальный и конечный индексы для поиска внутри массива. 2. Проверим базовый случай, если начальный индекс больше либо равен конечному, то возвращаем -1, так как элемент не найден. 3. Вычисляем средний индекс, как сумму начального и конечного индексов, разделенную на 2. 4. Если элемент с индексом `mid` равен `k`, то возвращаем `mid`. 5. Если элемент с индексом `mid` меньше `k`, то рекурсивно вызываем функцию `binary_search`, передавая начальный индекс `mid + 1` и конечный индекс. 6. Если элемент с индексом `mid` больше `k`, то рекурсивно вызываем функцию `binary_search`, передавая начальный индекс и конечный индекс `mid - 1`. 7. Если ни одно из условий не выполнилось, то возвращаем -1. Пример кода на языке Python: ```python def binary_search(arr, k, start, end): if start >= end: return -1 mid = (start + end) // 2 if arr[mid] == k: return mid elif arr[mid] < k: return binary_search(arr, k, mid + 1, end) else: return binary_search(arr, k, start, mid - 1) # Пример использования arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] k = 7 result = binary_search(arr, k, 0, len(arr) - 1) if result != -1: print(f"Элемент {k} найден. Индекс: {result}") else: print(f"Элемент {k} не найден.") ``` В данном примере представлен массив `[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]` и ищется элемент равный 7. Результатом будет "Элемент 7 найден. Индекс: 6". Если элемента с таким значением нет, то результат будет "Элемент 7 не найден."