二进制搜索compareTo字符串对象

class ObjectBinarySearcher{ 

    public static int search(String[] array, String value){ 

     int first = 0, last = array.length-1, position = -1; 
     boolean found = false; 

     while(!found && first < last){ 
      int mid = (first+last)/2; 
      int midValue = array[mid].compareTo(value); 

      if(midValue==0){ 
       position = mid; 
       found = true; 
      } 
      else if(midValue<0) 
       last = mid-1; 
      else 
       first = mid+1; 
     } 

     return position; 
    } 
}

我发送一个包含{“love”，“hate”，“happy”，“sad”，“neutral”}的数组，每次尝试使用我的二进制搜索方法来搜索“中性”，它告诉我它没有找到。是什么导致了这种情况发生？二进制搜索compareTo字符串对象

来源

2016-10-13 Nicholai Tukanov

是您的输入数组排序？你是否发送了[[“开心”，“憎恨”，“爱”，“中性”，“悲伤”]？ – Jason

是的，排序是我的主要方法。 –

更改while loop到while(!found && first <= last)

来源

2016-10-13 00:50:08 Libby

你输入数组必须按顺序使用二进制搜索排序。
正如@Libby指出的那样，您的while循环需要更改为允许first小于或等于last。
如果first == last没有找到匹配项，您需要能够退出循环。
如果midValue < 0您需要移动下限而不是上限（反之亦然）。

新的代码：

while (!found && first <= last) { // allow first to be lower or equal to last 
    int mid = (first + last)/2; 
    int midValue = array[mid].compareTo(value); 

    if (midValue == 0) { // matched! 

     position = mid; 
     found = true; 

    } else if (first == last) { // didn't match and there was only one left to check 

     break; // so break out of the loop 

    } else if (midValue < 0) { // current pos is too low 

     first = mid + 1; // so adjust the lower bound 

    } else { // current pos is too high 

     last = mid - 1; // so adjust the upper bound 

    } 
}

来源

2016-10-13 01:02:16 Jason

我添加了另一个终止的情况下，但它仍然告诉我，中立没有找到。另外，正如我所说的@Jason，它是我的主要方法排序。 –

编辑修复您的问题 - 当数组项目过低（反之亦然）时，您正在移动上限，这与您需要执行的操作相反。 – Jason

通过这种方式，它在元素4处找到“中性”，但是现在在重新运行搜索（使用do-while循环）之后，它现在在元素4处指示“伤心”。 –

二进制搜索compareTo字符串对象

回答

相关问题