Question:
How to speed up the code? When I / O changes, the system refuses to accept, so you need to leave the untouched Scan. At the moment it takes 1070 ms, it needs to be accelerated to 1000 ms. Any ideas are welcome!
import java.util.Scanner;
class Main {
public static boolean find(int search, int[] arr, int len) {
boolean ret = false;
int fst = 0;
int lst = len - 1;
if ( arr != null){
while (fst <= lst) {
int mid = (fst + lst) >>> 1;
if (search == arr[mid]) {
ret = true;
break;
} else if (search < arr[mid]) {
lst = mid - 1;
} else {
fst = mid + 1;
}
}
}
return ret;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int len = scan.nextInt();
int[] arr = new int[len];
int i;
for (i = 0; i < len; i++) {
arr[i] = scan.nextInt();
}
int num = scan.nextInt();
int search;
for (i = 0; i < num; i++) {
search = scan.nextInt();
System.out.print((find(search, arr, len))? "YES\n" : "NO\n");
}
}
}
Answer:
Without touching the actual dichotomous search, I will propose modifications:
//убран лишний параметр len + упрощаем вызов private дешевле public
private static boolean find(int search, int[] arr) {
//boolean ret = false; //лишняя декларация - фтопку
int mid;
if ( arr == null)
return false;
int fst = 0;
int lst = arr.length - 1;
while (fst < lst) {
mid = (fst + lst) >>> 1; //убираем декларацию mid - зачем нам лишнее движение в стеке?
if (search == arr[mid])
return true; //убираем break
else if (search < arr[mid])
lst = --mid;
else
fst = ++mid;
}
if(search==arr[fst]) //улучшаем асимптотику - то есть последний проход, когда fst==lst выносим за цикл
return true;
return false;
}