알고리즘 이진 검색-PHP开发-php.cn

알고리즘 이진 검색

高洛峰

풀어 주다： 2016-12-19 16:19:49

원래의

1703명이 탐색했습니다.

이진 검색은 절반 검색이라고도 합니다. 이진 검색의 기본 아이디어는 사전에 있는 요소가 작은 것부터 큰 것까지 순서대로 배열(array)에 저장되어 있다고 가정하는 것입니다. > 먼저, 고정된 값 키를 사전의 중간 위치에 있는 요소의 키와 비교합니다. 동일하면 검색에 성공합니다.

그렇지 않으면 키가 작으면 바이너리입니다. 검색은 사전의 전반부에서 계속됩니다.

키가 크면 사전의 후반부에서 이진 검색을 계속합니다.

이런 방식으로 한 번의 비교 후에 검색 간격이 절반으로 줄어들고 검색이 성공하거나 실패할 때까지 계속됩니다.

짝수의 중간 2개 요소 중 하나를 중간 요소로 취함

이진 검색은 시퀀스 테이블의 키를 기준으로 사전을 정렬해야 하는 보다 효율적인 검색 방법입니다. .

java 코드

위치를 성공적으로 반환하고, 실패하면 음수를 반환합니다.

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));  
      
    }  
 }

로그인 후 복사

더 보기 다중 알고리즘 이등분법에 대한 관련 기사를 찾으려면 PHP 중국어 웹사이트를 주목하세요!