编程知识 cdmana.com

Xiaobai understands the binary query algorithm

   Recently, we've done a lot of algorithms , I found myself forgetting a lot ; Quickly brush a few times to consolidate the memory , By the way, I would like to make a simple sharing , I hope I can help some friends !

One . Introduction

   Binary query is a query algorithm with high efficiency for query elements , Also known as “ The binary algorithm ”.

Two . Premise

   One of the most important preconditions for binary queries is The set or sequence to query It has to be Orderly

3、 ... and . The query process

  The process of binary query :

  1). Determine a query value

  2). Find the middle value in the sequence

  3). Compare the query value with the intermediate value , Two results :

    》 identical , It's worth finding

    》 inequality , Zoom out 1/2 The scope of , Repetition 2).3) To

Four . illustration ( Picture source Baidu )

  5、 ... and . Code implementation

   The idea of flying in the sky , In the end, it has to be realized on the ground . Or it's blowing water , Use language Java To achieve , There are two ways : Recursion and while Turn around .

   Recursive implementation of binary query

    /**
     *      Using recursion to implement binary query 
     * @param sortedArr: An ordered array of queries 
     * @param key: Query value , Nowadays, most people call them keywords , use key Express 
     * @param low: Starting point 
     * @param high: The end 
     * @return
     */
    public static boolean binarySearchByRecursion(int[] sortedArr, int key, int low, int high) {
        
        /**
         *      Check :
         *         1. If  key > sortedArr[high], The value must not be found 
         *         2. If  key < sortedArr[low], The value must not be found 
         *         3. If low > high, Logic doesn't hold , There is no intermediate value .
         */    
        if(key < sortedArr[low] || key > sortedArr[high] || low > high) {
            return false;
        }
        
        /**
         *      Get the index of the middle value , There are two results :
         *         1. Odd number .java The default is rounded down , It's OK to take an odd number as an intermediate index 
         *         2. Even number . Take even numbers   perhaps   Even number +1  Will do . Even numbers are taken here 
         */
        
        int mid = (high+low)/2;    // Get the index of the middle value 
        
        /*
         *      Determine the query value and intermediate value 
         *         1.  Query value  >  Median , The starting point narrows to the right , Call this method back 
         *         2. Query value  <  Median , The end point narrows to the left , Call this method back 
         *         3. Query value  =  Median , Value found 
         */
        
        if(key == sortedArr[mid]) {    // Query value  =  Median 
            return true;    // return true
        }else if(key > sortedArr[mid]) {    // Query value  >  Median 
            // The starting point narrows the scope 
            low = mid + 1; 
            // Recursively calls this function 
            return binarySearchByRecursion(sortedArr,key,low,high);
        }else if(key < sortedArr[mid]){    // Query value  <  Median 
            // The end point narrowed down 
            high = mid - 1; 
            // Recursively calls this function 
            return binarySearchByRecursion(sortedArr,key,low,high);    
        }
        
        return false;
    }

  main Method test :

    public static void main(String[] args) {
        // Prepare an ordered array 
        int[] sortedArr = new int[] {1,2,3,4,5,6,7,8,9,10,11,12,13,14};
        
        // Prepare a query value 
        int key = 2;
        // Prepare the starting and ending positions 
        int low = 0;
        int high = sortedArr.length-1;
        
        // Calling the binary query method returns a brin identifier ,true -  On behalf of finding ,false The representative couldn't find 
        boolean result = binarySearchByRecursion(sortedArr,key,low,high);
        
        // Printing results 
        if(result) {
            System.out.println(" There is... In the sequence "+key);
        }else {
            System.out.println(" There is no... In the sequence "+key);
        }
        
    }

   while Implement binary query

    public static boolean binarySearchByWhile(int[] sortedArr, int key, int low, int high) {
        /**
         *      Check :
         *         1. If  key > sortedArr[high], The value must not be found 
         *         2. If  key < sortedArr[low], The value must not be found 
         *         3. If low > high, Logic doesn't hold , There is no intermediate value .
         */    
        if(key < sortedArr[low] || key > sortedArr[high] || low > high) {
            return false;
        }
        
        while(low<=high) {    // Meet the starting point <= The end can go on , Because there is a middle value between the two 
            // Get the middle subscript 
            int mid = (high+low)/2;
            
            // if key = sortedArr[mid]
            if(key == sortedArr[mid]) {
                return true;
            }else if(key > sortedArr[mid]) {    // if key > sortedArr[mid]
                // Narrow the starting point 
                low = mid + 1;
            }else if(key < sortedArr[mid]){        // if key < sortedArr[mid]
                // Narrow the finish line 
                high = mid -1;
            }
        }
        // No return found false
        return false;
    }

  main Method test :

    public static void main(String[] args) {
        // Building an ordered array 
        int[] sortedArr = new int[] {1,2,3,4,5,6,7,8,9,10};
        // Create query values 
        int key = 10;
        // Establish a starting point and an end point 
        int low = 0;
        int high = sortedArr.length-1;
        // Call binary query method , return true On behalf of finding , Otherwise, we can't find 
        boolean result = binarySearchByWhile(sortedArr,key,low,high);
        // Printing results 
        if(result) {
            System.out.println(" There is... In the sequence "+key);
        }else {
            System.out.println(" There is no... In the sequence "+key);
        }
    }

   If there's anything wrong with it , Welcome to leave a message below to correct !

   If you think it's good , Use your little hand and point a recommendation to support the author

版权声明
本文为[itread01]所创,转载请带上原文链接,感谢

Scroll to Top