An example of java dichotomy algorithm

An example of java 2 algorithm

1. Premise: 2 points search premise is that the array to be searched must be sorted, our implementation here is ascending by default

2. Principle: the array is divided into three parts, which are the first, the second and the third of the median. The value to be searched is compared with the median of the array. If it is less than the median, it is searched before the median; if it is greater than the median, it is searched after the median; if it is equal to the median, it is returned directly. This is followed by a recursion, with the first half or the second half broken down into three parts. May not be very clear description, if you do not understand can go to the Internet. From the description, it can be seen that this algorithm is suitable to be implemented recursively, and anything that can be implemented recursively can be implemented in a loop. So our implementation is either recursive or circular, and we can understand the algorithm according to the code

3. Realization:

The following code

 
package org.cyxl.algorithm.search; 
 
/** 
 * 2 searching  
 * @author cyxl 
 * 
 */ 
public class BinarySearch { 
  private int rCount=0; 
  private int lCount=0; 
   
  /** 
   *  Get the number of recursions  
   * @return 
   */ 
  public int getrCount() { 
    return rCount; 
  } 
 
  /** 
   *  Number of times to get the loop  
   * @return 
   */ 
  public int getlCount() { 
    return lCount; 
  } 
 
  /** 
   *  Perform recursion 2 Subsearch, return the 1 The position where the value occurs next  
   * @param sortedData   Sorted arrays  
   * @param start      The starting position  
   * @param end       End position  
   * @param findValue    The value you want to find  
   * @return        The position of the value in the array from 0 Start. Unable to find return -1 
   */ 
  public int searchRecursive(int[] sortedData,int start,int end,int findValue) 
  { 
    rCount++; 
    if(start<=end) 
    { 
      // Middle position  
      int middle=(start+end)>>1;  // The equivalent of (start+end)/2 
      // The median  
      int middleValue=sortedData[middle]; 
       
      if(findValue==middleValue) 
      { 
        // Is equal to the median value returned directly  
        return middle; 
      } 
      else if(findValue<middleValue) 
      { 
        // If it's less than the median, look before the median  
        return searchRecursive(sortedData,start,middle-1,findValue); 
      } 
      else 
      { 
        // If it's greater than the median, look after the median  
        return searchRecursive(sortedData,middle+1,end,findValue); 
      } 
    } 
    else 
    { 
      // Can't find  
      return -1; 
    } 
  } 
   
  /** 
   *  cycle 2 Subsearch, return the 1 The position where the value occurs next  
   * @param sortedData   Sorted arrays  
   * @param findValue    The value you want to find  
   * @return        The position of the value in the array from 0 Start. Unable to find return -1 
   */ 
  public int searchLoop(int[] sortedData,int findValue) 
  { 
    int start=0; 
    int end=sortedData.length-1; 
     
    while(start<=end) 
    { 
      lCount++; 
      // Middle position  
      int middle=(start+end)>>1;  // The equivalent of (start+end)/2 
      // The median  
      int middleValue=sortedData[middle]; 
       
      if(findValue==middleValue) 
      { 
        // Is equal to the median value returned directly  
        return middle; 
      } 
      else if(findValue<middleValue) 
      { 
        // If it's less than the median, look before the median  
        end=middle-1; 
      } 
      else 
      { 
        // If it's greater than the median, look after the median  
        start=middle+1; 
      } 
    } 
    // Can't find  
    return -1; 
  } 
} 

4. Test the code

package org.cyxl.algorithm.search.test; 
 
import org.cyxl.algorithm.search.BinarySearch; 
import org.junit.Test; 
 
 
public class BinarySearchTest { 
  @Test 
  public void testSearch() 
  { 
    BinarySearch bs=new BinarySearch(); 
     
    int[] sortedData={1,2,3,4,5,6,6,7,8,8,9,10}; 
    int findValue=9; 
    int length=sortedData.length; 
     
    int pos=bs.searchRecursive(sortedData, 0, length-1, findValue); 
    System.out.println("Recursice:"+findValue+" found in pos "+pos+";count:"+bs.getrCount()); 
    int pos2=bs.searchLoop(sortedData, findValue); 
     
    System.out.println("Loop:"+findValue+" found in pos "+pos+";count:"+bs.getlCount()); 
  } 
} 

5, summary: this way of finding the use of the occasion for sorted array. You can see that the recursion and the loop have the same number of times

The above is the example of java 2 points detailed explanation, if you have any questions, please leave a message or to this site community exchange discussion, thank you for reading, I hope to help you, thank you for your support to this site!