二分算法，80分TLE求助

WilliamYuanBao @ 2024-07-14 13:24:04

#include <bits/stdc++.h>
using namespace std;

int search(int list_size,int nums[], int target) {
    int left = 0, right = list_size - 1, mid,qsxb;

    while (left <= right) {
        mid = left + (right - left) / 2; // 防止溢出
        if (nums[mid] == target) {
            qsxb = mid;
            if (mid != 0){ // 找到第一个答案 
                for (int i=mid-1;i>0;i--){
                    if (nums[i] != target){  
                        break;
                    } else {
                        qsxb = i;
                    }
                }
            }
            return qsxb+1; // 目标值在中间，返回索引
        } else if (nums[mid] < target) {
            left = mid + 1; // 目标值在右半区，更新左边界
        } else {
            right = mid - 1; // 目标值在左半区，更新右边界
        }
    }

    return -1; // 未找到目标值
}

int main() {
    int a[100000],n,m;
    scanf("%d %d",&n,&m);

    for (int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for (int i=0;i<m;i++){
        int q;
        scanf("%d",&q);
        int s;
        s = search(n,a,q);
        printf("%d ",s);
    }
    return 0;
}

by AndyZong @ 2024-07-14 13:27:03

STL是个好东西

by XuYueming @ 2024-07-14 13:32:14

@WilliamYuanBao 你这分了个寂寞啊

by WilliamYuanBao @ 2024-07-14 14:00:55

@AndyZong 我想用二分

by dogjuan @ 2024-07-14 14:27:13

建议不要在二分中特判然后去找第一个答案，如果全是一样的数字话的肯定就T掉了。 推荐这么写

while (L <= R) 
{
  int mid = (L + R) / 2;
  if (check(mid))
    R = mid - 1;
  else
    L = mid + 1;
}
cout<<L;//or R

而且真的没必要写那么长的变量名

by qw0er2ty1ui3 @ 2024-07-14 14:34:27

#include <bits/stdc++.h>
using namespace std;

int a[1000000],n,m;

int search(int list_size,int nums[], int target) {
    int left = 0, right = list_size - 1, mid;

    while (left < right) {//这才是找第一个目标值的方法
        mid = (right + left) / 2; 
        if (nums[mid] < target) {
            left = mid + 1; 
        } else {
            right = mid;
        }
    }
    if (nums[left]==target) {
            return left+1;
    } else return -1; 
}

int main() {
    scanf("%d %d",&n,&m);

    for (int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    for (int i=0;i<m;i++){
        int q;
        scanf("%d",&q);
        int s;
        s = search(n,a,q);
        printf("%d ",s);
    }
    return 0;
}

by WilliamYuanBao @ 2024-07-14 15:13:33

谢谢大家！我已关注你们~

by WilliamYuanBao @ 2024-07-14 19:19:50

本人已AC，谢谢（*\^_\^*）