Измененный двоичный поиск java

Question

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

Я пытаюсь изменить BinarySearch так, что он получит два индекса.

Первый индекс представляет собой самый дальний левый индекс числа заданной, х, и самый дальний вправо. Если число не существует, оно производит [-1, -1].

Anyways. Я пытаюсь изменить BinarySearch и не могу заставить его работать. Любые указатели будут очень благодарны.

public static Pair BinarySearchDup(int[] A, int x, int low, int high){ 
    int mid = (low + high)/2; 
    int left = -1, right = -1; 
    while(low <= high){ 
     mid = (low + high)/2; 
     if(A[mid] == x){ 
      int newMid = mid; 
      //check left 
      if(left == -1){ 
       left = mid; 
       return BinarySearchDup(A, x, low, mid - 1); 
      } 
      else if(right == -1){ 
       right = mid; 
       return BinarySearchDup(A, x, newMid + 1, high); 
      }  
      return new Pair(left, right); 
     } 
     else if(A[mid] < x) 
      return BinarySearchDup(A, x, mid + 1, high); 
     else// (A[mid] > x) 
      return BinarySearchDup(A, x, low, mid - 1); 
    } 
    //if there are no matches of the number then it returns -1 
    return new Pair(-1, -1); 
} 

Answer 1

Чтобы решить эту проблему:

Я пытаюсь изменить BinarySearch так, что она получит два индекса. Первый индекс - самый дальний левый указатель числа, данного, x и самого дальнего права. Если число не существует, оно производит [-1, -1].

Я хотел бы сделать это:

1) У бинарного поиска, за исключением того, вместо того, чтобы рассматривать цель на матч и заканчиваются сразу же, считаю, что это больше, чем ваша цель (например, вы поиск слева от него) , Когда этот поиск заканчивается, он будет либо в самом левом экземпляре цели, один слева (в зависимости от того, как он закодирован - в этом случае просто проверьте один справа), или будет подтверждено, что он не существует.

2) Сделайте двоичный поиск, как в 1), за исключением того, что цель меньше вашей цели. Аналогичным образом вы найдете самый правый экземпляр вашей цели.

Это дает вам сложность O (logN). Идея Петра Иванова «Разве вы не можете просто использовать обычный бинарный поиск, а затем просто идти туда и обратно от найденного индекса, пока не получите весь диапазон?» может быть столь же плохим, как и O (N), если в массиве имеется огромное количество дубликатов. Однако, если ожидаемое количество дубликатов (или ожидаемый размер массива) невелико, то идея Петра Иванова гораздо проще кодировать, поскольку вам не нужно переделывать бинарный поиск с измененной логикой.

Answer 2

Я не уверен, я понимаю вашу мысль, но вот почему он не работает:

Ваш код эквивалентен:

public static Pair BinarySearchDup(int[] A, int x, int low, int high){ 
    int mid = (low + high)/2; 
    if(low <= high){   
     if(A[mid] == x) 
      return BinarySearchDup(A, x, low, mid - 1); 
     else if(A[mid] < x) 
      return BinarySearchDup(A, x, mid + 1, high); 
     else// (A[mid] > x) 
      return BinarySearchDup(A, x, low, mid - 1); 
    } 

    return new Pair(-1, -1);   
} 

В самом деле, если вы входите в то время как loop, вы всегда возвращаетесь, поэтому не более одной итерации. Также, если значение в середине равно x, тогда, поскольку слева -1, вы всегда вводите это предложение if. Альтернативно, если вы не вводите цикл while, вы просто возвращаете (-1, -1). Надеюсь, это поможет.

EDIT: Не можете ли вы просто использовать обычный бинарный поиск, а затем просто идти туда и обратно от найденного индекса, пока не получите весь диапазон?