洛谷官方题单[Java版题解]--【算法1-6】二分查找与二分答案

知识点:二分查找快读一个大数字(防止MLE和TLE)这题是典型的二分查找的题目,先去带大家学习一下二分查找的基本代码,最好不要去直接调用Arrays.binarySearch,而是要去手写二分完整代码package love15; public class Main { public static void main(String[] args) { //这里先去讲下二分查找的基础知识 //二分查找就是就是去找在一个升序数组中,指定元素下标索引的位置 //关于二分查找我的思想是一种叫做舍弃的思想,就是我先找到数组的中间位置. // 如果我要找的元素,在我中间位置的右边,我就把中间位置左边(包括中间位置)的全部丢弃,因为左边的元素对我来说没有意义 //同理如果我要找的元素在中间位置的左边,我就把中间位置右边(包括中间位置)的全部丢弃,因为右边的对我没有任何意义 //多说无益,下面是代码演示 //一定要注意数组一定是升序 int []arrnew int[]{1,4,5,7,8,9,10,11}; System.out.println(binarySearch(arr, 10));//6 } public static int binarySearch(int []arr, int target){ int rightarr.length-1;//最右边的元素下标 int left0;//最左边的元素下标 while(leftright){ int mid(leftright)/2; if(arr[mid]target){ return mid; } else if(arr[mid]target) { rightmid-1; } else { leftmid1; } } //没有找打返回-1 return -1; } }接下来是本题的完整代码解析:注意本题是去找第一个数字出现的位置(lowerBound)//Java中的lowerBound和upperBound必须自己去手写import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class Main { //这里要去用快读,不要用Scanner,因为 纯整数 数据量大≥ 10^5→ 用快读否则 Scanner 会 TLE MLE。 //快读标准模板 static class Read { StreamTokenizer st new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); //这个StreamTokenizer会自动把你要读取的字符解析为有意义的token,比如字符123解析为123(double类型的) //字符13.3解析为13.3(doble) //这里只推荐用与数字格式的字符串 //如果这里你要写成long类型的,就用double去强转为long即可,因为double的数据范围远大于long public int nextInt() throws IOException { st.nextToken(); //默认是double类型,要强转为int return (int) st.nval;//num value } } public static void main(String[] args) throws IOException { //然后就是正常的创建对象,和Scanner二分查找即可 Read sc new Read(); int nsc.nextInt(); int msc.nextInt(); int []arrnew int[n1]; for (int i 1; i arr.length; i) { arr[i]sc.nextInt(); } for (int i0;im;i){ int asc.nextInt(); System.out.print(binarySearch(arr, a) ); } } public static int binarySearch(int []arr,int target){ int rightarr.length-1; int left1; int ans-1; while(leftright){ int mid(leftright)/2; if(arr[mid]target){ //找到了继续找,直到找到第一个 //写一个标准的二分查找函数,找不到返回-1即可 //然后他这本题我们注意是去找第一次这个元素出现的位置 //找到了,继续去找,就可以找打第一次出现的地方 ansmid; rightmid-1; } else if(arr[mid]target){ leftmid1; } else if(arr[mid]target){ rightmid-1; } } return ans; } }知识点:二分查找(手写左边界第一次出现于右边界最后一次出现)与时间复杂度分析(最小范围,最大范围)注意看本题的数据是2e5,这说明你用普通的双层循环O(n方)(5000)是肯定不行的此时有种想法是根据时间复杂度去猜,你大概要去用什么算法发现在2e5上面的不就只有 nlogn[5e5,5e6]和n[5e6,5e7],log(n)(1e18);法一:过了%70的测试点,就是双层循环(O(n方,5000)),根据题目去模拟即可,要注意题目并没有说是数组是有序还是无序的,要自己先去排序package love16; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; public class Main { //本题的是10的5次方读取数据要用快读 static class Read { StreamTokenizer st new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public int nextInt() throws IOException { st .nextToken(); return (int) st.nval; } } public static void main(String[] args) throws IOException { Read scnew Read(); int nsc.nextInt(); int csc.nextInt(); int []arrnew int[n]; for (int i 0; i n; i) { arr[i]sc.nextInt(); } Arrays.sort(arr); int count0; for(int i0;in;i){ for(int jarr.length-1;ji;j--){ if(arr[j]-arr[i]c){ count; } } } System.out.println(count); } }法二:利用二分查找,手写算法去找lowerBound和upperBound这里注意int的范围是-2e9,long的范围是-9e18import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; import java.util.Arrays; public class Main { //本题的是10的5次方读取数据要用快读 static class Read { StreamTokenizer st new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); public int nextInt() throws IOException { st.nextToken(); return (int) st.nval; } } public static void main(String[] args) throws IOException { Read sc new Read(); int n sc.nextInt(); int c sc.nextInt(); int[] arr new int[n]; for (int i 0; i n; i) { arr[i] sc.nextInt(); } Arrays.sort(arr);//nlogn; long count0; //int的范围是_2e9 //long的范围是_9e18 //本题count的最大范围是2e5*2e54e10一定会超的 //所以count要开long for (int i : arr) { int aic; int AlowerBound(arr,a); int BupperBound(arr,a); if(A-1||B-1){ continue; } count(B-(A-1)); } System.out.println(count); } //lowerBound 计算第一次出现的位置,左边界 public static int lowerBound(int[] arr, int target) { int left 0; int right arr.length - 1; int ans -1; while (left right) { int mid (left right) / 2; if (arr[mid] target) { ans mid; //找到了继续去找 right mid - 1; } else if (arr[mid] target){ leftmid1; }else { rightmid-1; } } return ans; } //upperBound 计算最后一次出现的地方 public static int upperBound(int []arr,int target){ int rightarr.length-1; int left0; int ans-1; while (leftright){ int mid(leftright)/2; if (arr[mid]target){ ansmid; leftmid1; } else if(arr[mid]target){ leftmid1; } else { rightmid-1; } } return ans; } }