二分検索ソート(JAVA)

最悪の場合:
logn
最良の状況:O(1)
平均時間複雑度O(logn)
二分ルックアップは、折半ルックアップ、または対半ルックアップとも呼ばれ、効率の高いルックアップ方法です.
要件:
(1)順序記憶構造を採用する必要がある(2).キーワードサイズ順に並べなければならない
n個の要素をほぼ等しい2つの部分に分け、a[n/2]をxと比較し、x=a[n/2]であればxを見つけ、アルゴリズムは中止する.
x>a[n/2]の場合、配列aの左半分でxを検索し続け、x
2つのクエリは、ループと再帰の2つの方法で構成されます.
再帰二分検索:

/**
	 * @Descript:      (   ，  -1，    ，    )
	 *
	 * @author LJonah 2018 3 1 
	 * @param array
	 *              
	 * @param searchData
	 *                 
	 * @param begin
	 *                
	 * @param end
	 *                
	 * @return
	 */
	public static int recursiveBinarySearch(int[] array, int searchData, int begin, int end) {
		//                                 ，     ，  -1
		if (searchData < array[begin] || searchData > array[end] || begin > end)
		return -1;
		int mid = (begin + end) / 2;
		System.out.println("   mid=" + array[mid]);
		if (array[mid] == searchData)
			return mid;
		else if (array[mid] < searchData)
			return recursiveBinarySearch(array, searchData, mid + 1, end);
		else
			return recursiveBinarySearch(array, searchData, 0, mid);
	}

循環二分検索:

/**
	 * @Descript:      (   ，  -1，    ，    )
	 *
	 * @author LJonah 2018 3 1 
	 * @param array
	 *              
	 * @param searchData
	 *                 
	 * @param begin
	 *                
	 * @param end
	 *                
	 * @return
	 */
	public static int loopBinarySearch(int[] array, int searchData, int begin, int end) {
	    int beginIndex = begin;
	    int endIndex = end;
	    //              ，  -1
	    while(beginIndex <= endIndex && (searchData > array[beginIndex] && searchData < array[endIndex])){
	    	int mid = (beginIndex+endIndex)/2;
	    	System.out.println("   mid="+array[mid]);
	    	//                   ,     ，  -1
	    	if(array[mid] == searchData)
	    		return mid;
	    	else if(array[mid] < searchData)
	    		beginIndex = mid+1;
	    	else
	    		endIndex = mid;
	    }
	    return -1;
	}

テスト:

public static void main(String[] args) {
		//           ，            
		int[] array = { 0, 3, 4, 8, 9 };
		int searchData =4;
		System.out.println("    ：" + Arrays.toString(array) + ";   ：" + searchData + ";");
		//       
		int index = recursiveBinarySearch(array, searchData, 0, array.length - 1);
		if (index > -1)
			System.out.println(searchData + "   " + Arrays.toString(array) + "     ：" + index);
		else
			System.out.println("   ！");
		//       
		index = loopBinarySearch(array, searchData, 0, array.length - 1);
		if (index > -1)
			System.out.println(searchData + "   " + Arrays.toString(array) + "     ：" + index);
		else
			System.out.println("   ！");

	}

テスト結果:

    ：[0, 3, 4, 8, 9];   ：4;
   mid=4
4   [0, 3, 4, 8, 9]     ：2
   mid=4
4   [0, 3, 4, 8, 9]     ：2