이분 찾기 와 이분 답

머리말
주의: 사람마다 각자 의 작법 이 있 습 니 다.이 중요 하고 기본 적 인 점 은 호랑이 형 과 야 오 씨 는 모두 상대방 이 말 했다 고 생각 했 지만 아무 도 말 하지 않 았 다.그러나 야 오 씨 의 2 분 의 답 을 나 는 이해 할 수 없다.
이분 찾기
2 분 검색 은 절반 검색, 2 분 검색 이 라 고도 부 르 며 질서 있 는 배열 에서 특정한 요 소 를 찾 는 알고리즘 입 니 다.이 는 배열 의 현재 부분의 중간 요 소 를 고찰 할 때마다 중간 요 소 를 찾 으 려 면 검색 과정 을 끝 냅 니 다.중간 요소 가 찾 은 값 보다 작 으 면 왼쪽 에 있 는 요 소 는 더 작 을 뿐 찾 을 수 없 는 요 소 는 오른쪽 에서 찾 으 면 됩 니 다.만약 에 중간 요소 가 찾 은 값 보다 크 면 오른쪽 요 소 는 더 크 고 찾 지 못 하 는 요소 만 있 기 때문에 왼쪽 에서 찾 아야 합 니 다.code:

int Search (int l,int r,int x)
{
      int mid;
      while(l<=r)
      {
            mid=l+((r-l)>>1);
            if(a[mid]x) mid=r+1;
            else if(a[mid]==x) return mid;
      }
      return -1;
}

주의 하 세 요. 이곳 의 질 서 는 넓 은 의미 의 질서 입 니 다. 만약 에 한 배열 의 왼쪽 이나 오른쪽 이 특정한 조건 을 만족 시 키 지 못 하면 다른 한 측 이 이런 조건 을 만족 시 키 지 못 하면 질서 (만족 조건 을 1 로 보고 만족 하지 않 으 면 0 를 만족 시 키 지 않 은 다음 에 Check (mid) 를 추가 하 는 것 으로 볼 수 있 습 니 다.따라서 2 분 검색 법 은 특정한 조건 을 만족 시 키 는 최대 (최소) 의 값, 즉 2 분 의 답 을 찾 을 수 있다.
이분 답
이러한 '최대 치 최소 화' 문 제 를 2 분 검색 법 으로 풀 려 면 다음 과 같은 세 가지 조건 을 만족 시 켜 야 한다. 1. 답 은 고정 구간 에 있다.2. 조건 에 부합 되 는 값 을 찾 는 것 은 쉽 지 않 을 수 있 지만 특정한 값 이 조건 에 부합 되 는 지 여 부 를 쉽게 판단 할 수 있어 야 한다.3. 구간 에 대해 일정한 단조 성 을 만족 시 킬 수 있다.다시 말 하면 x 조건 에 부합 한다 면 x+1 또는 x-1 도 조건 에 부합 한 다 는 것 이다.(이렇게 내 려 오 면 위 에서 언급 한 단조 성 을 만족 시 킬 수 있다)
왼쪽 합 법 최대 치
code:

int Search(int l,int r)
{
      ++r;//    
      int mid;
      while(l+1>1);
            if(Check(mid)) l=mid;//l      
            else r=mid;
      }
      return l;//    
}

왜 이리 저리 닫 고 저리 열 어
끝까지 찾 으 면 이렇게 되 기 때문이다.
합 법 적
합 법 적
합 법 적
합 법 적
비합법적
비합법적
비합법적
최소 값
···
l
mid
r
···
최대 치
혹시
합 법 적
합 법 적
합 법 적
비합법적
비합법적
비합법적
비합법적
최소 값
···
l
mid
r
···
최대 치
그리고
합 법 적
합 법 적
합 법 적
비합법적
비합법적
비합법적
최소 값
···
l\mid
r
···
최대 치
혹시
합 법 적
합 법 적
합 법 적
비합법적
비합법적
비합법적
최소 값
···
l
r\mid
···
최대 치
시 뮬 레이 션 은 정확 하지만 왜 왼쪽 닫 기 오른쪽 닫 기 가 아 닙 니까?답 이 최대 치 라면 wa 이기 때문이다.
오른쪽 합 법 적 인 최소 값
code

int Search(int l,int r)
{
      --l;//    
      int mid;
      while(l+1>1);
            if(Check(mid)) r=mid;//r      
            else l=mid;
      }
      return r;//    
}

왜 이리 저리 열 고 저리 닫 느 냐
끝까지 찾 으 면 이렇게 되 기 때문이다.
비합법적
비합법적
비합법적
비합법적
합 법 적
합 법 적
합 법 적
최소 값
···
l
mid
r
···
최대 치
혹시
비합법적
비합법적
비합법적
합 법 적
합 법 적
합 법 적
합 법 적
최소 값
···
l
mid
r
···
최대 치
그리고
비합법적
비합법적
비합법적
합 법 적
합 법 적
합 법 적
최소 값
···
l\mid
r
···
최대 치
혹시
비합법적
비합법적
비합법적
합 법 적
합 법 적
합 법 적
최소 값
···
l
r\mid
···
최대 치
시 뮬 레이 션 은 정확 하지만 왜 왼쪽 닫 기 오른쪽 닫 기 가 아 닙 니까?답 이 최소 치 라면 wa 이기 때문이다.