二分查找的两种实现方式--循环和递归

矫情吗；* 2022-09-25 06:14 121阅读 0赞

package com.ming.test;
    
    import java.util.Arrays;
    
    public class binarySearch {
    	public static int binarySearch(int[] srcArray, int des) {
    		// 第一个位置.
    		int low = 0;
    		// 最高位置.数组长度-1,因为下标是从0开始的.
    		int high = srcArray.length - 1;
    		// 当low"指针"和high不重复的时候.
    		while (low <= high) {
    			// 中间位置计算(high+low)/2
    			int middle = (high + low) / 2;
    			// 与最中间的数字进行判断,是否相等,相等的话就返回对应的值.
    			if (des == srcArray[middle]) {
    				return srcArray[middle];
    				// 如果小于的话则移动最高层的"指针"
    			} else if (des < srcArray[middle]) {
    				high = middle - 1;
    				// 移动最低的"指针"
    			} else {
    				low = middle + 1;
    			}
    		}
    		return -1;
    	}
    
    	/**
    	 * 递归方法实现二分查找法.
    	 * 
    	 * @param Array数组
    	 
    	 * @param key
    	 *            要查找的值.
    	 */
    	public static int Search(int Array[], int low, int high, int key) {
    		if (low <= high) {
    			int mid = (low + high) / 2;
    			if (key == Array[mid])
    				return Array[mid];
    			else if (key < Array[mid])
    				// 移动low和high
    				return Search(Array, low, mid - 1, key);
    			else if (key > Array[mid])
    				return Search(Array, mid + 1, high, key);
    		}
    
    		return -1;
    
    	}
    
    	public static void main(String[] args) {
    		int srcArray[] = { 1, 25, 24, 12, 69, 2, 2, 4 };
    		Arrays.sort(srcArray);
    		System.out.println(Search(srcArray, 0, srcArray.length, 12));
    		System.out.println(binarySearch(srcArray, 0));
    
    	}
    
    }