二分法-和为给定数

红太狼 2023-07-09 13:26 42阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 1]

import java.util.Arrays;
    import java.util.Scanner;
    
    public class 和为定数 {
        
        static int N=100000+5;
        static int [] num=new int[N];
        static int n,m;
        static int f(int x)
        {
        
            int l=0,r=n,mid;
            //l，r，mid，左右边界和中间点
            while(l<=r)
            {
        
                mid=l+(r-l)/2;
                if(num[mid]==x)return mid;
                if(num[mid]<x)l=mid+1;
                if(num[mid]>x)r=mid-1;
            }
            return 0;
        }
        public static void main(String[] args) {
        
            Scanner sc=new Scanner(System.in);
            n=sc.nextInt();
    //        int [] a=new int [n];
            for (int i = 0; i <n ; i++) {
        
                num[i]=sc.nextInt();
            }
            m=sc.nextInt();
            Arrays.sort(num,0,n);
            for(int i=0;num[i]<=m/2;i++)
            {
        //遍历比m/2小的数字
                int t=f(m-num[i]);//寻找是否存在这个数
                if(t>0&&t!=i)//题目要求是数据对，所以自己和自己不行t!=i
                {
        
                    System.out.printf("%d %d",num[i],m-num[i]);
                    System.exit(0);
                }
            }
            System.out.println("No");
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200314200244357.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200314200250832.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzY3MzE1Ng==,size_16,color_FFFFFF,t_70