알고리즘 이분법 찾기

2548 단어 알고리즘
본 고 는 자바 를 이용 하여 이분법 검색 사상 을 실현 합 니 다. 이분법 검색 알고리즘 에서 수열 은 이미 순 서 를 정 했 습 니 다. 검색 할 숫자 에 대해 우 리 는 중간 숫자 부터 검색 합 니 다. 만약 에 목표 수가 중간 수 보다 적 으 면 오른쪽 수 를 검색 할 필요 가 없습니다. 오른쪽 수 는 중간 수 보다 많 기 때문에 왼쪽 수 를 직접 검색 하면 됩 니 다.만약 에 목표 수가 중간 수 보다 크 면 왼쪽 의 수 를 검색 할 필요 가 없다. 왼쪽 의 수 는 모두 중간 수 보다 작 기 때문에 오른쪽 에 있 는 수의 주 의 를 직접 검색 하 는 곳 이다. 1. 수열 은 순 서 를 배열 하 는 것 이다. 그렇지 않 으 면 이분법 으로 2. 수열 에 있 는 요소 의 값 을 찾 을 수 없고 3. 주의 if 문장의 판단 방식 을 반복 할 수 없다.결과 알고리즘 시간 복잡 도와 공간 복잡 도: 1. 최 악의 경 우 는 첫 번 째 요소 나 최 악의 요 소 를 찾 는 것 입 니 다. T (n) = O (logn) 2. 가장 좋 은 경 우 는 가장 중간 요 소 를 찾 는 것 입 니 다. O (1) 공간 복잡 도 는 S (n) = n 자바 코드 로 이 루어 집 니 다.
/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int i=1;
        int j=n;
        int mid=0;
        //       
        while(i<=j){
            //    
            mid=(j-i)/2+i;
            //guess(int num)                      
            int val=guess(mid);
            //-1              
            if(val==-1)
            j=mid-1;
            else if(val==1)
            //+1              
                i=mid+1;
                else 
                return mid;
        }

        return -1;
    }
}
[연습] POJ - 3461 Oulipo (KMP / 문자열 해시)
Gatsby에 Commento(또는 기타 주석)를 추가하는 방법

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage