Algorithm binary search-PHP开发-php.cn

Algorithm binary search

高洛峰

Release： 2016-12-19 16:19:49

Original

1701 people have browsed it

Binary search is also called half search. The basic idea of binary search is to assume that the elements in the dictionary are stored in an array (array) in an orderly manner from small to large.

First, the given value key and the middle value of the dictionary are Compare the keys of the elements at the position. If they are equal, the retrieval is successful;

Otherwise, if the key is small, continue the binary search in the first half of the dictionary;

If the key is large, then search in the second half of the dictionary Continue the binary search in .

In this way, the search interval is reduced by half after one comparison, and this continues until the search is successful or fails.

Take any one of the middle 2 elements from an even number as the middle element

Binary retrieval is a more efficient retrieval method, which requires the dictionary to be sorted by key in the sequence table.

java code

Returns to the location successfully, returns a negative number on failure

package ForTest;  
  
import java.util.ArrayList;  
import java.util.Arrays;  
import java.util.List;  
  
public class Arithmetic{  
      
    public static<T extends Comparable<? super T> > int BinarySearch(List<T> array, int start, int end, T key)  
    {         
        int low;  
        int high;         
        int guess;  
          
        if(array == null || start>end || start > array.size()-1 || end < 0)  
        {  
            return -1;  
        }    
          
        start = start < 0 ? 0 : start;  
        low  = start-1;  
          
        end = end > array.size()-1 ? array.size()-1 : end;   
        high = end+1;   
          
          
        while (high - low > 1) {  
            guess = ((high - low)>>1)  + low;  
  
            if (array.get(guess).compareTo(key) < 0)  
                low = guess;  
            else  
                high = guess;  
        }  
  
        if (high == end +1 )  
        {  
             return ~(end +1 );  
        }             
        else if (array.get(high).compareTo(key) == 0)  
        {  
             return high;  
        }  
        else  
        {  
            return ~high;         
        }        
    }  
    public static<T extends Comparable<? super T> > int BinarySearch(T[] array, int start, int end, T key)  
    {     
        List<T> stooges = Arrays.asList(array);  
        return Arithmetic.BinarySearch(stooges, start, end, key);  
    }  
      
      
    public static void main(String[] args) {  
        // TODO Auto-generated method stub  
          
        ArrayList<Integer> a = new ArrayList<Integer>();  
          
        Float[] b = new Float[100];  
       
          
        for(int i=0; i<100; i++)  
        {  
            a.add(i);    
            b[i] = (float) i;  
              
        }         
          System.out.println(""+Arithmetic.BinarySearch(a,0,1000,200));  
          System.out.println(""+Arithmetic.BinarySearch(b,0,100,2.f));  
      
    }  
 }

Copy after login

For more articles related to the dichotomy of the algorithm, please pay attention to the PHP Chinese website!