0

下面是一个二进制搜索算法，但它没有找到值：

我不认为这个算法是正确的？

'theArray' 被初始化为一个 0 的数组，其中位置 7 的项等于 4。

object various {

  //O(log N)

  def binarySerachForValue(value : Int) = {

    var arraySize = 100
    var theArray = new Array[Int](arraySize)
    theArray(7) = 4
    var timesThrough = 0
    var lowIndex = 0
    var highIndex = arraySize - 1

    while(lowIndex <= highIndex){
        var middleIndex = (highIndex + lowIndex) / 2

        if(theArray(middleIndex) < value)
            lowIndex = middleIndex + 1
        else if(theArray(middleIndex) > value)
            highIndex = middleIndex - 1

        else {
            println("Found match in index " + middleIndex)
            lowIndex = highIndex + 1
        }

        timesThrough = timesThrough + 1

    }

    timesThrough
  }                                               //> binarySerachForValue: (value: Int)Int
    binarySerachForValue(4)                       //> res0: Int = 7
}
4

3 回答 3

1

假设您的数组已经正确排序，您可以使用尾优化递归将您的搜索函数编写得更具功能性，如下所示：

def binarySearchForValue(value : Int, theArray:Array[Int]) = {        
  @tailrec
  def doSearch(arr:Array[Int], index:Int = 0):Int = {        
    val middleIndex = arr.size / 2
    val splits = arr.splitAt(middleIndex)
    val totalIndex = middleIndex + index
    arr(middleIndex) match{
      case i if i == value => totalIndex
      case i if i < value => doSearch(splits._2, totalIndex)
      case _ => doSearch(splits._1 dropRight(1), totalIndex)
    }
  }
  doSearch(theArray)
}

请注意，这也可以稍微不同地完成，如下所示：

def binarySearchForValue(value : Int, theArray:Array[Int]) = {        
  @tailrec
  def doSearch(low:Int, high:Int):Int = {
    val mid = (low + high) / 2
    if(mid >= theArray.size) -1 
    else {
        val currval = theArray(mid)
        if (currval == value) mid
        else if (currval < value) doSearch(mid+1, high)
        else doSearch(low, mid - 1)
    }
  }
  doSearch(0, theArray.size)
}
于 2013-09-12T23:35:03.260 回答
0

循环应该是这样的：

while(lowIndex <= highIndex){
    //note the lowIndex + other
    var middleIndex = lowIndex + ((highIndex + lowIndex) / 2)

    if(theArray(middleIndex) < value)
        lowIndex = middleIndex + 1
    else if(theArray(middleIndex) > value)
        highIndex = middleIndex - 1

    else return middleIndex 

    timesThrough = timesThrough + 1

}
// if loop finished and not returned middleIndex in last else, return -1 (not found)
return -1
于 2013-09-12T23:03:57.273 回答
0

它看起来像是二进制搜索算法的正确实现，但您提供了一个 0 数组，索引为 7 处只有一个数字。二进制搜索通常需要一个排序值数组（尽管您可以将排序作为第一步实现）。

这是一个为什么首先需要排序数组的示例：

搜索(4)

theArray = [0,4,0,0,0]

第一次迭代，看 theArray(2)，它等于 0. 0 < 4，所以使用上半部分（即下索引 = 中索引 + 1

新数组 = [0,0]

然后我们再次迭代并最终退出循环，因为我们从未找到它。使用排序列表，您的技术会很好用。

在 0 数组中查找单个值时，最好的办法是遍历数组直到找到它。祝你好运。

于 2013-09-12T23:13:19.040 回答