题目描述
JAVA 二分递归实现
JAVA 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
InputStreamReader in = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(in);
String str[] = br.readLine().split(" ");
int n = Integer.parseInt(str[0]);
int m = Integer.parseInt(str[1]);
int arr[] = new int[n];
str = br.readLine().split(" ");
for (int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(str[i]);
}
while (m-- != 0) {
int k = Integer.parseInt(br.readLine());
int res = bSection(arr, 0 ,n-1, k);
if(res == -1) System.out.println("-1 -1");
else {
int res_2 = bSection_2(arr, 0, n-1, k);
System.out.println(res+" "+res_2);
}
}
}
private static int bSection(int[] arr, int l, int r, int k) {
if(l >= r && arr[l] != k) return -1;
if(l == r && arr[l]==k)return l;
int mid = l+r>>1;
if(arr[mid] >= k) {
r = mid;
}
else {
l = mid+1;
}
return bSection(arr, l, r, k);
}
private static int bSection_2(int[] arr, int l, int r, int k) {
if(l >= r && arr[l] != k) return -1;
if(l == r && arr[l]==k)return l;
int mid = l+r+1>>1;
if(arr[mid] <= k){
l = mid;
}
else {
r = mid-1;
}
return bSection_2(arr, l, r, k);
}
}