二分搜索算法

二分搜索算法

題目：設 a [ 0 : n - 1 ] 是一個已排好序的數組。請改寫二分搜索算法，使得當搜索元素 x 不在數組中時，返回小於 x 的最大元素的位置 i 和大於 x 的最小元素位置 j 。當搜索元素在數組中時， i 和j相同，均為 x 在數組中的位置。並對自己的程序進行復雜性分析。

import java.util.Arrays;
import java.util.Scanner;

public class Main {

	static int x;// 需要查找的數據

	// 形參i,j是數組下標，arr是原數組，answer是存儲答案的數組
	static void getij(int i, int j, int[] arr, int[] answer) {
		if (i > j) {
			// x不在數組中的情況
			answer[0] = j;
			answer[1] = i;
			return;
		}
		int len = j - i + 1;// 加不加1都可以

		if (x == arr[len / 2 + i]) {
			// x在數組中的情況
			Arrays.fill(answer, len / 2 + i);// java api 方法,作用是將數組answer裡的元素都賦值為len/2+1
		} else if (x < arr[len / 2 + i]) {
			getij(i, len / 2 + i - 1, arr, answer);
		} else {
			getij(len / 2 + i + 1, j, arr, answer);
		}
	}

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);

		while (scanner.hasNext()) {
			int n = scanner.nextInt();

			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = scanner.nextInt();
			}

			x = scanner.nextInt();

			// 答案 存儲的是數組下標 i = answer[0]; j = answer[1]
			int[] answer = new int[2];
			getij(0, n - 1, arr, answer);// 0,n-1都是數組的下標

			System.out.println(answer[0] + " " + answer[1]);
		}
		scanner.close();
	}
}