알고리즘-이분탐색(Binary Search)

이분탐색:정렬할수있는 배열에서 기준을 가지고 이분하면서 탐색하는 방법 시간복잡도는 O(log N)
오름차순 배열의 특징
i번 인덱스에있는 a[i]가 j보다 크다면 a[j+1,j+2,...]는 a[i]보다 모두 크다.
i번 인덱스에있는 a[i]가 j보다 작다면 a[j-1,j-2,...]는 a[i]보다 모두 작다.
boj 7795

import java.util.*;
import java.io.*;

public class bs1 {

    public static int n,m;
    public static int[] a,b;
    static FastReader fr= new FastReader();

    static void input(){
        n=fr.nextInt();
        m=fr.nextInt();
        a=new int[n+1];
        b=new int[m+1];
        for(int i=1;i<=n;i++){
            a[i]=fr.nextInt();
        }
        for(int j=1;j<=m;j++){
            b[j]=fr.nextInt();
        }
    }
    static void pro(){
        Arrays.sort(b,1,m+1);
        int ans=0;
        for(int i=1;i<=n;i++){
            //a[i]를 선택 했을때 B에서는 a[i]보다 작은 몇게인지 count
            ans+=lower_bound(b,1,m,a[i]);
        }
        System.out.println(ans);
    }
    static int lower_bound(int[] a, int l, int r, int x){
        int result=l-1;
        while(l<=r){
            int mid=(r+l)/2;
            if(a[mid]<x){
                result=mid;
                l=mid+1;
            }else if (a[mid]>=x){
                r=mid-1;
            }
        }
        return result;
    }
    public static void main(String[] args) {
        int TT;
        TT = fr.nextInt();
        for (int tt = 1; tt <= TT; tt++) {
            input();
            pro();
        }
    }
    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}