求助！全re 萌新刚学二分

gwynplaine123 @ 2024-02-15 18:42:29

#include<iostream>
using namespace std;
const int N=1000010;
int num[N], target, q, n, x;
int search(int num[], int n, int target)  
{
    int left = 1;
    int right = n - 1;
    int mid;
    while (left <= right)
    {
        mid = left + ((right - left) / 2);
        if (num[mid] > target)
        {
            right = mid - 1;
        }
        else if (num[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            return mid;
        }
    }
    return -1;
}
int main()
{
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> num[i];
    while (q--)
    {
        cin >> target;
        x = search(num, n, target);
        cout << x << " ";
    }
    return 0;
}

by kevinZ99 @ 2024-02-15 18:50:34

@gwynplaine123

#include<iostream>
using namespace std;
const int N=1000010;
int num[N], target, q, n, x;
int search(int num[], int n, int target) 
{
    int left = 1;
    int right = n;//这里是n 
    int best=-1;
    while (left <= right)
    {
        int mid = (left+right)/2;
        if (num[mid] > target)
        {
            right = mid - 1;
        }
        else if (num[mid] < target)
        {
            left = mid + 1;
        }
        else{
            best=mid;
            right=mid-1;//有相等的可能，如果搜到的不是第一个那么就错了，所以要继续往前 
        }
    }
    return best;
}
int main(){
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> num[i];
    while (q--)
    {
        cin >> target;
        x = search(num, n, target);
        cout << x << " ";
    }
    return 0;
}

by QWQ_123 @ 2024-02-15 18:51:13

@gwynplaine123 二分要具有单调性，然而您没有排序不具有单调性

by QWQ_123 @ 2024-02-15 18:53:14

然后他要求的是第一次出现的位置，然而您这个求的是它任意出现的位置，所以要把同样的数缩成一个二元组 \{a,b\} 表示 a 这个数第一次出现在 b，然后按照 a 排序再二分即可。

当然还有 @kevinZ99 dalao 说的 r=n

by kevinZ99 @ 2024-02-15 18:56:17

@QWQ_123 他题目说了单调的

by QWQ_123 @ 2024-02-15 19:12:54

@kevinZ99 没看见（/jk

by kevinZ99 @ 2024-02-15 19:23:54

@QWQ_123 没事我天天不开long long

by gwynplaine123 @ 2024-02-15 23:59:27

@kevinZ99 谢谢您！