Двоичный поиск квадратного корня из leetcode oj

Question

public static int sqrt(int x) { 

    if(x == 0 || x == 1){ 
     return x; 
    } 
    long start = 0; 
    long end = x; 


    while (end-start > 1){ 
     long mid = (int)(end + start)/2; 
     long s = mid * mid; 

     if(s == x){ 
      return (int)mid; 
     } 
     else if(s > x){ 
      end = mid; 
     } 
     else { 
      start = mid; 
     } 

    } 

    return (int)start; 
    } 

Выше приведен фрагмент рабочего кода. У меня есть вопросы, как показано ниже. Заранее благодарю за помощь. ;-)

1. В то время как (конечный старт> 1) зачем нам 1 здесь? просто потому, что знак возврата является int?
2. Если мы сменим цикл while (конец-конец> 1) на (end> start), мы должны сделать end = mid-1; и start = mid + 1, правильно? Еще одно шаговое движение, я задаюсь вопросом, связано ли это также с возвратом типа integer?
3. Почему мы не можем вернуть end? или (int) (начало + конец)/2 ?? Я видел почти 99% ответов, возвращенных в левую границу бинарного поиска. Я просто хочу знать, верно ли возвращение к правильной границе или к среднему?

Answer 1

Возвращаемый тип int просто означает, что вы вернуть результат, который имеет тип int. Он не имеет ничего общего с алгоритмом внутри тела метода. Ниже я попытался ответить на ваши вопросы:

1. While(end-start > 1) используется, чтобы убедиться, end всегда больше, чем start. если end-start составляет 1 или меньше 1, это означает, что вы достигли конца бинарного поиска.
2. Вы можете изменить и изменить while(end-start > 1) на номер while(end > start), он по-прежнему будет работать. Не нужно делать end = mid-1 и начать = mid+1.
3. Все зависит от того, где вы отвечаете ложью. Это может быть различным для каждой проблемы.

Попробуйте использовать приведенную ниже ссылку, чтобы лучше понять алгоритм бинарного поиска.

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

Надеется, что это помогает.