알고리즘 2 분 검색 버 전

2 분 검색 에 대해 서 는 잘 알 고 있 을 것 입 니 다. 에서 언급 한 것 처럼 간단 한 프로그램 이지 만 bug 가 없 는 버 전 을 실현 하 는 것 은 쉬 운 일이 아 닙 니 다. 필 자 는 최근 에 2 분 검색 을 보고 간략하게 요약 해 보 았 습 니 다.
서로 다른 수요 에 대해 우리 가 직면 한 2 분 의 1 을 찾 으 면 서로 다른 버 전이 있 을 것 이다. 내 가 최근 에 만난 몇 가지 버 전에 대해 잘 설명해 보 자.

 하나의 배열 을 지정 합 니 다. 이 배열 에 어떤 요소 elem 이 존재 하 는 지 찾 습 니 다. 이 요 소 를 되 돌려 주 는 아래 표 시 를 가지 고 있 으 면 되 돌아 오 는 - 1 이 존재 하지 않 는 다 면.

이것 은 가장 흔히 볼 수 있 는 버 전 으로 코드 도 그리 어렵 지 않다.가장 흔히 볼 수 있 는 코드 는 다음 과 같다.
배열 A [left, right] 에서 원소 m 를 찾 습 니 다.

int binarySearch(int A[], int left, int right, int target)
{
    int mid;
    if(left > right) 
    {
        cout << "find range error!" << endl;
        return -1;
    }
    while(left <= right) //             [ left， right ]    ，                      
    {
        mid = left + (right-left)/2; //    
        assert( ( A[left] <=  A[mid] )  && (  A[mid] <= A[right] )); //        
        if ( A[mid] == target ) return mid;
        else if( A[mid] > target ) right = mid-1;
        else left = mid + 1;
    }
    cout << target << " not exist in A" << endl;
    return -1;

}

2 분 검색 의 재 귀 실현: (대부분의 경우 재 귀 가 적용 되 지 않 고 재 귀 함수 호출 비용 이 비교적 크 지만 여기 서 재 귀 버 전 을 실현 합 니 다.)

int binarySearchRecursion(int A[],int left, int right,int m)
{
    if(left <= right)
    {
        int mid = left + (right-left)/2;
        if(A[mid] == m) return mid;
        else if(A[mid] > m)
        {
            right = mid-1;
            binarySearchRecursion(A,left,right,m);
        }
        else
        {
            left = mid+1; 
            binarySearchRecursion(A,left,right,m);
        }
    }
    //      else，           ，      ，     -1！！
    else
    {
        return -1;
    }
}

한 배열 A 를 지정 하고 이 배열 에 특정한 요소 elem 이 존재 하 는 지 2 분 으로 찾 습 니 다. 이 요소 가 처음 나타 난 다음 표 시 를 되 돌려 주 는 것 이 존재 하지 않 으 면 되 돌려 주 는 - 1 이 존재 하지 않 습 니 다.메모: 우선 이 배열 에 이러한 요소 elem 이 존재 하 는 지 확인 하고 시작 위 치 를 찾 아야 합 니 다.코드 는 다음 과 같 습 니 다.

int binarySearchStartPos(int A[], int left, int right, int m)
{
    int mid, tmid ;
    if(left > right)
    {
        cout << "find range error !!" << endl;
        return -1;
    }
    while(left <= right)
    {
        mid = left + (right-left)/2;
        if(A[mid] == m)    //                  m，           ，         -1.
        {
            tmid = mid;
            //       ，      ：[left right]            m。
            //           。    left right                   ！！！
            right = mid-1;
            while(left <= right)
            {
                mid = left + (right-left)/2;
                if(A[mid] ==  m){right = mid-1;tmid = mid;}
                else if (A[mid] < m) left = mid + 1;
                else;
            }
            return tmid;
        }
        else if(A[mid] > m) right = mid-1;
        else left = mid+1;
    }
    cout << m << "not exist in A " << endl;
    return -1;
}

주의: 이곳 의 모든 범위 의 축 소 는 상기 2 분 검색 과 다 릅 니 다. 배열 에 요소 m 가 존재 하 는 지 확인 한 후에 모든 단계 의 범 위 는 요소 m 가 반드시 고찰 하 는 하위 배열 에 있어 야 합 니 다.2 분 검색 의 최적화 문제 도 매우 중요 하 다. 2 분 검색 자체 의 시간 복잡 도 는 이미 매우 좋 지만 서로 다른 응용 에 대해 서로 다른 최적화 방식 을 사용 할 수 있다.예 를 들 어 (right - left) / 2 는 자 리 를 옮 겨 실현 하거나 배열 의 상하 표 가 경 계 를 넘 지 않도록 left + (right - left) / 2 를 사용 하여 실현 할 수 있다.월경 을 피하 다.