이산 검색

Question

예를 들어 discrete binary search을 설명해 주실 수 있습니까?

나는 위의 링크에서 그것에 대해 읽었으며 그것이 무엇인지에 대한 기본적인 아이디어를 얻었지만 코드 부분과 실제로 어떻게 구현되는지 이해하지 못합니다.

Answer 1

는 기본적

• 당신이 함수 F를 추정 (x)는 단조 간격 는 (감소) 증가 된 [A, B].
• F (A) < C < F (b)는
당신은 X 찾으려면
• F (X) = C.

이 그럼 당신은 X를 찾기 위해 이진 검색을 사용할 수 있도록. 본질적으로 변수 x의 가능한 간격의 절반을 매번 사용합니다.

#define EPS 1E-9 

double f(double x) 
{ 
    ///some monotonically increasing function on [a, b], for example f(x) = x^3: 
    return x*x*x; 
} 

double binarySearch(double C, double a, double b) 
{ 
    double low = a, high = b; 
    double mid; 
    while(abs(low-high) > EPS) 
    { 
     mid = low + (high - low)/2; 
     if f(mid) < C 
      low = mid; 
     else 
      high = mid; 
    } 
    return mid; 
}