Java binary search implementation principle and code implementation

1. Description of binary search steps

(1) First determine the middle position of the entire search interval mid = (left right)/2

(2) Use The keyword value to be searched is compared with the keyword value in the middle position;

If they are equal, the search is successful

If it is greater, continue the search in half in the last (right) half area

If it is less than, continue the half search in the front (left) half area

(3) Press the half formula again for the determined reduced area, and repeat the above steps.

Finally, the result is obtained: either the search is successful or the search fails. The storage structure of binary search is stored in a one-dimensional array. Example of half search algorithm

2. Requirements

(1) A sequential storage structure must be used.

(2) Must be arranged in order by keyword size.

3. Example

public class Demo {
 
    public static void main(String[] args) {
        int[] arr={-1,0,3,5,9,12};//查找的数组
        int searchNum=13;//查找的目标数
        Arrays.sort(arr);
 
        int resultOne=binarySearchOne(arr,searchNum,0,arr.length-1);
        System.out.println(resultOne);
 
        int resultTwo=binarySearchTwo(arr,searchNum);
        System.out.println(resultTwo);
    }
 
    /**
     * 递归实现
     * @param arr
     * @param searchNum
     * @param start
     * @param end
     * @return
     */
    public static int binarySearchOne(int[] arr,int searchNum,int start,int end){
        if(start>end)
            return -1;
        int middle=(start+end)/2;
        if(searchNum<arr>arr[middle])
            return binarySearchOne(arr,searchNum,middle+1,end);
        else
            return middle;
    }
 
    /**
     * 非递归实现
     * @param arr
     * @param searchNum
     * @return
     */
    private static int binarySearchTwo(int[] arr, int searchNum) {
        int start=0;
        int end=arr.length-1;
        while(startarr[middle])
                start=middle+1;
            else
                return middle;
        }
        return -1;
    }
}</arr>

The above is the detailed content of Java binary search implementation principle and code implementation. For more information, please follow other related articles on the PHP Chinese website!