2012-06-20 12:51:12Morris
[JAVA][考題] Binary Search 遞迴版本
教授考了這麼一題, 他沒有明確告訴我們陣列中的值是已經排好的 !
沒有 sort 過, 可不能做的, 而且並沒有告訴我們函數的參數, 因此是自由發揮,
不過我覺得課本上的寫法很囉唆, 原因在於, 如果 return 的話,
其實後面就不加上 else if 了
由於 競賽的時候, 有人簡寫成 bsearch, 那我也來試試 !
import java.util.Arrays;
public class BSearch {
public static int bsearch(int[] arr, int l, int r, int key) {
if(l > r)
return -1;
int m = (l+r)/2;
if(arr[m] == key)
return m;
if(arr[m] > key)
return bsearch(arr, l, m-1, key);
else
return bsearch(arr, m+1, r, key);
}
public static void main(String[] args) {
int[] arr = new int[10];
for(int i = 0; i < 10; i++) {
arr[i] = (int)(Math.random()*100);
}
Arrays.sort(arr);
for(int e : arr) {
System.out.print(e + ", ");
}
System.out.println("");
for(int e : arr) {
int idx = bsearch(arr, 0, arr.length, e);
System.out.print(e + " in arr[" + idx + "]\n");
}
int idx = bsearch(arr, 0, arr.length, -1);
System.out.print(-1 + " in arr[" + idx + "]\n");
}
}
沒有 sort 過, 可不能做的, 而且並沒有告訴我們函數的參數, 因此是自由發揮,
不過我覺得課本上的寫法很囉唆, 原因在於, 如果 return 的話,
其實後面就不加上 else if 了
由於 競賽的時候, 有人簡寫成 bsearch, 那我也來試試 !
import java.util.Arrays;
public class BSearch {
public static int bsearch(int[] arr, int l, int r, int key) {
if(l > r)
return -1;
int m = (l+r)/2;
if(arr[m] == key)
return m;
if(arr[m] > key)
return bsearch(arr, l, m-1, key);
else
return bsearch(arr, m+1, r, key);
}
public static void main(String[] args) {
int[] arr = new int[10];
for(int i = 0; i < 10; i++) {
arr[i] = (int)(Math.random()*100);
}
Arrays.sort(arr);
for(int e : arr) {
System.out.print(e + ", ");
}
System.out.println("");
for(int e : arr) {
int idx = bsearch(arr, 0, arr.length, e);
System.out.print(e + " in arr[" + idx + "]\n");
}
int idx = bsearch(arr, 0, arr.length, -1);
System.out.print(-1 + " in arr[" + idx + "]\n");
}
}