Что не так с моим двоичным кодом поиска java?

Question

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

public int binSearch(int empID) 
{ 
    int first = 0; 
    int last = empCount - 1; 
    int found = 0; 
    int mid = 0; 

    while (first <= last && found == 0) 
    { 
     mid = (first + last)/2; 

     if (empNums[mid] == empID) 
     { 
      found = 1; 
     } 
     else 
     { 
      if (empNums[mid] < empID) 
      { 
       first = mid + 1; 
      } 
      else 
      { 
       last = mid - 1; 
      } 
     } 
     while (found == 0) 
     { 
     mid = -1; 
     } 

    } 
    return mid; 

} 

Answer 1

Я серьезно не понимаю, почему вы положили, что while(found==0) цикл в середине функции, но это, безусловно, ведет к бесконечной петле. Просто попробуйте удалить его. Чтобы узнать, найдено ли решение, мы можем сделать метод return -1 в этом конкретном случае. Это условие нужно проверить только в конце функции. Я также поставил логический бит-сдвиг при вычислении вашего среднего индекса.

public int binSearch(int empID) 
{ 
    int first = 0; 
    int last = empCount - 1; 
    boolean found = false; 
    int mid = 0; 

    while (first <= last && !found) 
    { 
     mid = (first + last) >>> 1; // overflow prevention 

     if (empNums[mid] == empID) { 
      found = true; 
     } else if (empNums[mid] < empID) { 
      first = mid + 1; 
     } else { 
      last = mid - 1; 
     } 
    } 
    return found ? mid : -1; 
} 

Answer 2

Давайте посмотрим на этот сценарий этого: Ваша первая является 0, и ваш конец 1. то есть это: середина = 1 + 0/2 который всегда 0! это может привести к проблеме, потому что вы можете просто продолжать проверять одну и ту же позицию снова и снова.

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

Mid = Math.ceil (старт + конца)/2); P.S вам может понадобиться бросить !! Успехов

Answer 3

Я хотел бы предложить следующее:

public int binSearch(int empID) 
{ 
    int first = 0; 
    int last = empCount - 1; 
    int mid; 

    // check the first and last element, otherways it could take too long to get to them 
    if (empNums[first] >= empID) 
     mid = first; 
    else if (empNums[last] <= empID) 
     mid = last; 
    else 
     do { 
      mid = (first + last)/2; 
      // If you have found an element, just return it, no found variable is required  
      // And you do not want to add or subtract 1 from a limits, because 
      // next element could be one you looking for 
      if (empNums[mid] == empID) 
       return mid; 
      else if (empNums[mid] < empID) 
       first = mid; 
      else 
       last = mid; 
     } while (first < last); 

    // optional check to see that correct parameter has been found 
    if (empNums[mid] != empID) { 
     // do something 
    } 

    return mid; 
}