by : digitalevers scala, 教程&知识, 算法

日取其半-Scala实现顺序数列的二分查找

package com.datacrafts.digitalevers.test

class binaryFind(in:Array[Int]) {
  val src:Array[Int] = in

  /**
   * 给定一个整数 
   * 使用二分查找它在顺序数列中的位置
   * @param in
   * @return
   */
  def find(in:Int): Int = {
    var start_index = 0
    var end_index = src.length - 1
    var curr_index = (start_index + end_index) / 2
    //需要探测边界 否则无法检索到
    if(src(start_index) == in){
      return start_index
    }
    if(src(end_index) == in){
      return end_index
    }
    //查找中位数 如果没有查找到 继续循环这一过程 当开始节点靠近尾节点则跳出循环
    while(src(curr_index) != in && ((end_index - start_index) > 1)){
      if(src(curr_index) > in){
        end_index = curr_index
      } else {
        start_index = curr_index
      }
      curr_index = (start_index + end_index) / 2
    }
    //循环结束还没找到 说明不存在这一节点 以返回-1标识
    if(src(curr_index) != in){
      return -1
    }
    //查找到则返回该节点index索引
    curr_index
  }
}

object binaryFind{
  def main(args: Array[String]): Unit = {
    val bf = new binaryFind(Array(10,11,12,20))
    println(bf.find(21))
  }
}

上述算法对头尾节点进行了一次特殊的探测处理，因为如果目标值刚好落在头尾节点，最后当头尾节点相互靠近的时候，该算法的中间节点可能无法移动（会一直停留在头节点）从而导致死循环。为了避免死循环，故加上了靠近退出循环机制，但最后可能会无法查找到这个目标节点。

这种为特殊情况而加的代码处理使得整个算法看起来不再是一个“优秀”的算法，后来读到《编程珠玑》的算法，很巧妙地规避了这个问题——该书采取了将中间节点curr_index移动一位的做法，如果目标值比中间节点大，则curr_index往大方向移动一位，如果小，则反之往小的方向移动一位。这很好理解，也是很正确的做法。既然中间节点不是目标值，那为何还要将其作为新的起始节点呢

这种新算法不存在中间节点最后不移动的问题，所以也就不需要再对头尾节点进行探测处理了，并且也不需要再设置头尾节点靠近则退出循环的机制

精简后的代码如下

package com.datacrafts.digitalevers.test

class binaryFind(in:Array[Int]) {
  val src:Array[Int] = in

  /**
   * 给定一个整数
   * 使用二分查找它在顺序数列中的位置
   * @param in
   * @return
   */
  def find(in:Int): Int = {
      var start_index = 0
      var end_index = src.length - 1
      var curr_index = 0

      //查找中位数 如果没有查找到 继续循环这一过程 当开始节点靠近尾节点则跳出循环
      while(start_index <= end_index){
        curr_index = (start_index + end_index) / 2
        if(src(curr_index) > in){
          end_index = curr_index - 1
        } else if(src(curr_index) < in) {
          start_index = curr_index + 1
        } else {
          return curr_index
        }
      }
      //循环结束还没找到 说明不存在这一节点 以返回-1标识
      -1
  }
}

object binaryFind {
  def main(args: Array[String]): Unit = {
    val bf = new binaryFind(Array(10,11,12,20))
    println(bf.find(12))
  }
}
Leave a comment