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;

}