二分查找的递归与非递归方式-蒲公英云

二分查找的递归与非递归方式

二分查找的递归与非递归方式：

二分查找的前提条件是：
数组有序，不能有相同值。

如果有相同值，只能先进行二分查找，得到一个下标后，再根据这个下标在数组中左右遍历别的值是否相等。

测试代码：

import java.util.Arrays;
/* * 关于二分查找： * */
public class BinarySearchTest { 
    public static void main(String[] args) { 
        int[] arr = { -6, -1, 0, 3, 7, 12, 23, 55};
        int index1 = binarySearch(arr, 7, 0, arr.length-1);
        System.out.println(index1);
        int index2 = binarySearch02(arr, 55);
        System.out.println(index2);
        System.out.println("-------------------------------------------------------");
        int[] arr1 = { -1, 3, 6, 6, 4, 2, 1, 1, 4, 7, 6, 6, 6, 6, 4};
        //数组元素：-1 3 6 6 4 2 1 1 4 7 6 6 6 6 4
        //对应下标： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
        System.out.println(Arrays.binarySearch(arr1, 6));  //11
        System.out.println(Arrays.binarySearch(arr1, 4));  //8
        System.out.println(Arrays.binarySearch(arr1, 1));  //7
        //当元素有相同，且无序时，能找出其中一个值的下标，具体是哪一个，无法得知
        System.out.println("-------------------------------------------------------");
        //arr1排序后
        Arrays.sort(arr1);
        //数组元素：-1 1 1 2 3 4 4 4 6 6 6 6 6 6 7
        //对应下标： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
        System.out.println(Arrays.binarySearch(arr1, 6));  //11
        System.out.println(Arrays.binarySearch(arr1, 4));  //7
        System.out.println(Arrays.binarySearch(arr1, 1));  //1
        //当元素有相同，且无序时，能找出其中一个值的下标，具体是哪一个，也无法得知
    }
    //二分查找的递归方式
    private static int binarySearch(int[] arr, int num, int left, int right) { 
        if (left > right)   return -1;
        int middle = (left + right) / 2;
        if (arr[middle] == num) { 
            return middle;
        } else if (arr[middle] < num) { 
            return binarySearch(arr, num, middle + 1, right);
        }else{ 
            return binarySearch(arr, num, left, middle-1);
        }
    }
    //二分查找的非递归方式
    private static int binarySearch02(int[] arr, int num) { 
        int start = 0;
        int end = arr.length-1;
        while (start <= end) { 
            int middle = (start + end) / 2;
            if (arr[middle] > num) { 
                end = middle - 1;
            } else if (arr[middle] < num) { 
                start = middle + 1;
            } else { 
                return middle;
            }
        }
        return -1;
    }
}