查找数组的位置 - C++

Question

如您所见，我想找到给定数组的位置。

例如：

我有一个数组 {5 , 2, 3, 1} （我想决定我想猜多少）
- 然后程序会将其排序为 {1, 2, 3, 5}
- 最后，我将有机会猜测我想要猜多少次的数字（例如：我想要 2 个数字猜测，它们是 5 和 3。然后程序将搜索数字 5 和3. 程序会告诉我在排序数组中的位置。然后是“3 found at 3, 5 found at 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;
}

而这个 link 是我项目的完整问题： 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;
}

查找数组的位置 - C++

Finding location of an array - C++

c++

arrays

locate