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))
}
}
近期评论