바이너리 검색이 경우 작동하지 않습니까?

Question

https://leetcode.com/problems/guess-number-higher-or-lower-ii/#/description.

우리는 추측 게임을하고 있습니다. 게임은 다음과 같습니다 :

1에서 n까지 숫자를 선택합니다. 내가 선택한 번호를 맞춰야 해.

내가 잘못 생각할 때마다 내가 선택한 번호가 인지 여부를 알려줍니다.

그러나 특정 숫자 x를 추측하고 잘못 생각하면 $ x를 지불해야합니다. 내가 선택한 수를 추측하면 게임에서 이기게됩니다.

특정 n ≥ 1이 주어지면 승리를 보장하기 위해 필요한 금액 (최소)을 알아보십시오.

이 문제를 실천하고있었습니다. 이 문제는 이진 검색을 사용하여 해결할 수 있다고 생각했습니다. 특히, 최악의 경우, 번호는 항상 각 분할의 오른쪽 절반에 위치한다고 가정 할 수 있습니다.

예 : n = 5라고합시다. 그렇다면

[1, 2, 3, 4, 5]가 있습니다.

첫 번째 시도 = 3, 두 번째 시도 = 4. 이렇게하면 7 달러의 최악의 사례가 발생합니다. 그러나 솔루션을 살펴본 결과 동적 프로그래밍을 사용하는 것으로 보입니다. 이진 검색 알고리즘이이 경우 어떻게 작동하지 않는지 궁금합니다.

Answer 1

이진 검색을 사용하면 숫자를 찾기 위해 필요한 최소 회전 수를 찾을 수 있습니다.

[1,2,3 :하지만이 질문에 당신이 생각해야 할 비용이 작동하지 않습니다 이진 검색을 수행하는 예 부분 여기 if you guess wrong, you pay $x

에 의해 정의된다 number of turns 아니라 min sum that you pay in worst case됩니다 아니다 1,4]

최적의 전략 최악

pick(2) -> decision: target is bigger 
-> pick(3) -> decision: target is bigger [if decision is smaller thats not worst case] 
-> pick(4) -> done 

Total cost = 2+3 = 5 

BS에 사용 :

01,232,

최적의 전략을 위해서는 동적 프로그래밍 솔루션을 생각해 볼 필요가 있습니다. 당신의 질문은 왜 바이너리 검색이 최선의 전략으로 여기에서 작동하지 않는지에 대한 것입니다. 나는 단지 이것을 보여주는 예에 불과하고 DP 솔루션에 대해서는 설명하지 않을 것입니다.

Answer 2

도움이 될 수 있습니다. 바이너리 검색이 작동해야합니다.

public int guessNumber(int n) 
{ 
    int low=1; 
    int high=n; 

    while(low <= high){ 
     int mid = low+((high-low)/2); 
     int result = guess(mid); 
     if(result==0) 
     { 
      return mid; 
     } 
     else if(result==1) 
     { 
      low = mid+1; 
     } 
     else 
     { 
      high=mid-1; 
     } 
    } 

return -1; } 

Answer 3

귀하의 질문은 하나 개 때문에 큰 요인 이진 검색에 적용 할 수 없습니다 - 이진 검색 특정 번호를 찾을 수 있도록 할 필요가 시도의 수를 줄임에 집중 설계되었습니다.

이진 검색은 숫자를 찾기 위해 필요한 히트 수를 최소화합니다 (치는 값에 의존하지 않고). 그것과 함께 다른 요인을 최소화 할 수는 없습니다.

따라서 동적 프로그래밍을 사용하는 것이 좋습니다. 지불해야하는 최소 $ (누적 합계)를 찾으려는 경우에 유용합니다.