二分查找思想（使用递归和不适用递归的思想）

男娘i 2022-04-13 12:01 204阅读 0赞

![70][]

public class BinarySearch {
    	public static void main(String[] args) {
    		int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    		System.out.println(searchLoop(array, 101));
    	}
     
    	/**
    	 * 循环二分查找，返回第一次出现该值的位置
    	 * 
    	 * @param array
    	 *            已排序的数组
    	 * @param findValue
    	 *            需要找的值
    	 * @return 值在数组中的位置，从0开始。找不到返回-1
    	 */
    	public static int searchLoop(int[] array, int findValue) {
    		// 如果数组为空，直接返回-1，即查找失败
    		if (array == null) {
    			return -1;
    		}
    		// 起始位置
    		int start = 0;
    		// 结束位置
    		int end = array.length - 1;
    		while (start <= end) {
    			// 中间位置
    			int middle = (start + end) / 2;
    			// 中值
    			int middleValue = array[middle];
    			if (findValue == middleValue) {
    				// 等于中值直接返回
    				return middle;
    			} else if (findValue < middleValue) {
    				// 小于中值时在中值前面找
    				end = middle - 1;
    			} else {
    				// 大于中值在中值后面找
    				start = middle + 1;
    			}
    		}
    		// 返回-1，即查找失败
    		return -1;
    	}
    }
     
     
    使用递归实现折半查找
     
    	public static int binSearch(int array[],  int key) { 
    		int start = 0;
    		int end = array.length - 1;  
    		return binSearch(array,start,end,key);
        } 
    	/**
    	 * 递归折半查找
    	 * @param array
    	 * @param start
    	 * @param end
    	 * @param key
    	 * @return
    	 */
    	public static int binSearch(int array[], int start ,int end, int key) { 
            int mid = (end + start) / 2;   
            if (array[mid] == key) {   
                return mid;   
            }   
            if (start >= end) {   
                return -1;   
            } else if (key > array[mid]) {   
                return binSearch(array, mid + 1, end, key);   
            } else if (key < array[mid]) {   
                return binSearch(array, start, mid - 1, key);   
            }   
            return -1;   
        }

![70 1][]

[70]: /images/20220413/6e3422fbd6f843c3808b213ab71d0ab6.png
[70 1]: /images/20220413/11ec2325eca2416ea5fb326a22e96242.png