JAVA常用アルゴリズム一:二分検索【再帰or非再帰】

文書ディレクトリ

一、Java実現二分検索【再帰】

二、Java実現二分検索【非再帰】

三、テスト

一、Java実現二分検索【再帰】

	//        
	public static int binarySearchRecursion(int[] arr, int target, int left, int right) {
		if(left > right)
			return -1;
		int mid = (left + right) / 2;
		int midVal = arr[mid];
		if(target > midVal)
			return binarySearchRecursion(arr, target, mid + 1, right);
		else if(target < midVal)
			return binarySearchRecursion(arr, target, left, mid - 1);
		else 
			return mid;
	}

二、Java実現二分検索【非再帰】

	//         
	public static int binarySearch(int[] arr, int target) {
		int left = 0, right = arr.length - 1;
		while (left < right) {
			int mid = (left + right) / 2;
			int midVal = arr[mid];
			if(target < midVal)
				right = mid - 1;
			else if(target > midVal)
				left = mid + 1;
			else {
				return mid;
			}
		}
		return -1;
	}

三、テスト

	public static void main(String[] args) {
		int arr[]= { 1, 8, 10, 89, 1000,1000, 1234 };
//		System.out.println(binarySearchRecursion(arr, 89, 0, arr.length-1));
		System.out.println(binarySearch(arr, 89));
	}