JavaSE 第三十六讲 Java数组查找方式及二分查找剖析 10.26

1、数组查找

public class ArraySearchTest
{
    public static int search(int[] array, int value)
    {
        for(int i = 0; i < array.length; i++)
        {
            if(value == array[i])
            {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args)
    {
        int[] a = new int[]{1, 3, 5, 6, 7, 8, 10, 12, 15, 16, 19, 22, 23, 25}; 
        int value = 16;

        int index = search(a, value);

        System.out.println(index);

    }
}

2、二分查找

public class BinarySearch
{
    public static int search(int[] array, int value)
    {
        int low = 0;
        int high = array.length - 1;
        int middle;
    
        while(low <= high)
        {
            middle = (low + high) / 2;

            if(array[middle] == value)
            {
                return middle;
            }   

            if(value < array[middle])
            {
                high = middle - 1;
            }

            if(value > array[middle])
            {
                low = middle + 1;
            }
        
        }

        return -1;
    }

    public static void main(String[] args)
    {
        int[] a = new int[]{1, 3, 5, 6, 7, 8, 10, 12, 15, 16, 19, 22, 23, 25};

        int index = search(a, 15);

        System.out.println(index);
    }   
}

public class BinarySearch
{
    public static int search(int[] array, int value)
    {
        int low = 0;
        int high = array.length - 1;
        int middle;
    
        while(low <= high)
        {
            middle = (low + high) / 2;

            for(int i = 0; i < array.length; i++)
            {
                System.out.print(array[i]);

                if(i == middle)
                {
                    System.out.print("#");
                }   

                System.out.print(" ");
            }
                
            System.out.println();       

            if(array[middle] == value)
            {
                return middle;
            }   

            if(value < array[middle])
            {
                high = middle - 1;
            }

            if(value > array[middle])
            {
                low = middle + 1;
            }
        
        }

        return -1;
    }

    public static void main(String[] args)
    {
        int[] a = new int[]{1, 3, 5, 6, 7, 8, 10, 12, 15, 16, 19, 22, 23, 25};

        int index = search(a, 15);

        System.out.println(index);
        //C:\>java BinarySearch
        //1 3 5 6 7 8 10# 12 15 16 19 22 23 25
        //1 3 5 6 7 8 10 12 15 16 19# 22 23 25
        //1 3 5 6 7 8 10 12 15# 16 19 22 23 25
        //8
    }   
}