二分查找法（折半查找法）

╰半夏微凉° 2023-06-15 11:01 39阅读 0赞

### 要求：给定数组必须要是有序的（要么从小到大，要么从大到小排序）。 ###

--------------------

### 原理:二分法查找（Binary Search）也称折半查找，是指当每次查询时，将数据分为前后两部分，再用中值和待搜索的值进行比较，如果搜索的值大于中值，则使用同样的方式（二分法）向后搜索，反之则向前搜索，直到搜索结束为止。 ###

package com.bjsxt.test;
    
    /**
     * 二分查找法（要求：数组必须要是有序的）
     * @author Administrator
     *
     */
    public class BinarySearchDemo {
    
    	public static void main(String[] args) {
    		int[]nums= {1,3,5,9,22,29};
    		int i = binarySearch(nums, 0, nums.length-1, 9);
    		System.out.println("二分法查找到的索引值为="+i);
    		
    	}
    	
    	/**
    	 * 二分查找给定数所在的索引位置
    	 * @param nums 给定数组
    	 * @param start 起始位置所在的索引
    	 * @param last 数组最后一个位置所在的索引
    	 * @param searchNum 需要查找的数
    	 * @return 给定数所在数组中的索引值 如果没有查到为-1
    	 */
    	public static int binarySearch(int[]nums,int start,int last,int searchNum) {
    		//确保数组是有序数组
    		if(start<=last) {
    			//先获取中间索引值
    			int middleIndex=(start+last)/2;
    			//获取中间值
    			int middleNum= nums[middleIndex];
    			//如果该数小于中间值 就从前半截开始查（！别忘了return）
    			if(searchNum<middleNum) {
    				return binarySearch(nums, start, middleIndex-1, searchNum);
    			}else if(searchNum==middleNum) {
    				return middleIndex;
    			}else {
    				//如果给定数大于中间值，就从后半截开始查找
    				return binarySearch(nums, middleIndex+1, last, searchNum);
    			}
    		}
    		return -1;
    	} 
    
    }