Java二分法查找实现

时间:2021-11-21 22:09:44
public class Dichotomy {
    
    //定义查找次数
    static int count = 0;
    
    public static void main(String[] args) {
        
        //定义数组
        int [] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        
        //二分法查找
        int result = searchRecursive( array, 0, array.length - 1, 3);
        
        //打印结果
        System.out.println("二分法查找结果为=" + result);
        System.out.println("查找次数为=" + count);
    }
    
    /**
     * 执行递归二分查找,返回第一次出现该值的位置
     *
     * @param array
     *            已排序的数组
     * @param start
     *            开始位置
     * @param end
     *            结束位置
     * @param findValue
     *            需要找的值
     * @return 值在数组中的位置,从0开始。找不到返回-1
     */
    private static int searchRecursive(int[] array, int start, int end, int findValue) {
        
        //数组如果为空则返回-1
        if(array == null){
            
            return -1;
        }
        
        
        
        while(start <= end){
            
            count++;
            
            //获取中间位置
            int middle = (start + end) / 2;
            
            //获取中间值
            int middleValue = array[middle];
            
            if(middleValue == findValue){
                
                return middle;
            }else if(findValue < middleValue){
                
                end = middle - 1;
            }else{
                
                start = middle + 1;
            }
            
        }
        
        return -1;
    }
}