Поиск местоположения массива - C++

Question

Как вы можете видеть, я хочу найти местоположение данного массива.

Например:

• У меня есть массив {5, 2, 3, 1} (Я хочу, чтобы решить, сколько догадок я хочу угадать)
  • Затем программа сортирует его { 1, 2, 3, 5}
  • Наконец-то мне дадут шанс угадать число, которое я хотел, сколько угадывают (пример: я хочу, чтобы 2 числа догадывались, они 5 и 3. тогда программа будет найдите номер 5 и 3. Программа сообщит мне местоположение в отсортированном массиве. Затем оно «3 найдено по 3, 5 найдено по 4»

Однако, я мой код застрял в сортировочный

это мой код:

#include <iostream> 
using namespace std; 
int main(void) 
{ 
    int temp, i, j, n, list[100]; 
    cin>>n; 
    for(i=0; i<n; i++) 
    { 
     cin>>list[i]; 
    } 
    for(i=0; i<n-1; i++) 
     for(j=i+1; j<n; j++) 
      if(list[i] > list[j]) 
      { 
       temp = list[i]; 
       list[i] = list[j]; 
       list[j] = temp; 
      } 
    for(i=0; i<n; i++) 
     cout<<" "<<list[i]; 
    cout<<endl; 
    return 0; 
} 

И эта связь полный вопрос о моем проекте: http://uva.onlinejudge.org/external/104/p10474.pdf

Answer 1

В вашей функции сортировки нет проблем, кстати, вы можете решить оригинальную проблему в O(nlogn), ваш O(n^2)

код:

#include <iostream> 
#include <algorithm> 
using namespace std; 

int binary_search(int A[], int key, int imin, int imax) 
{ 
if (imax < imin) 
return -1; 
else 
{ 
    int imid = (imax + imin)/2; 

    if (A[imid] > key) 
    // key is in lower subset 
    return binary_search(A, key, imin, imid - 1); 
    else if (A[imid] < key) 
    // key is in upper subset 
    return binary_search(A, key, imid + 1, imax); 
    else 
    // key has been found 
    return imid; 
} 
} 


int main() { 
// your code goes here 
int n,q; 
while(1){ 
    cin >> n>> q; 
    if(n==0) 
    break; 
    int* a = new int[n]; 
    int i; 
    for(i=0;i<n;i++) 
    cin >> a[i]; 
    sort(a,a+n); 
    while(q--){ 
     int k; 
     cin >> k; 
     k=binary_search(a,k,0,n-1); 
     if(k==-1) 
     cout << "not found" << endl; 
     else 
     cout << "found at :" << k+1 << endl; 
    } 


} 
return 0; 
}