[AS3]使用黄金分割查找法来搜索数组的元素

需要FloatUtil.equals，请参照[AS3]判断两个浮点小数的数组是否相等。

Class : advancedflex.utils.FloatArrayUtil

/**
* 使用黄金分割查找法来搜索数组的元素。
*
* @param sortedArray 排成升序(从小到大)的数组。
* @param value 要查找的值。
* @param tol 浮点小数的计算误差。
* @return 元素的下标。如果没有，则返回 -1。
*/

public static function gsearch(sortedArray:Array, value:Number, tol:Number = 1e-12):int {
 if(!sortedArray) {
  throw new ArgumentError("Param: must not be null.");
 }
 return $gsearch(sortedArray, value, tol, 0, sortedArray.length);
}

/**
 * @private
 */
private static const $LEFT_RATIO:Number = 0.6180339887498949;

/**
 * @private
 */
private static const $RIGHT_RATIO:Number = 1 - $LEFT_RATIO;

 /**
 * @private
 * 使用黄金分割查找法来搜索数组的元素。
 * 
 * @param sortedArray 排成升序(从小到大)的数组。
 * @param value 要查找的值。
 * @param tol 浮点小数的计算误差。
 * @param left 查找的最左边。
 * @param right 查找的最右边。
 * @return 元素的下标。如果没有，则返回 -1。
 */
private static function $gsearch(
 sortedArray:Array, value:Number, tol:Number,
 left:int, right:int):int 
{
 if(right - left <= 1) {
  return FloatUtil.equals(sortedArray[left], value, tol) ? left :
   FloatUtil.equals(sortedArray[right], value, tol) ? left :
   -1;
 }
 var center:int = $RIGHT_RATIO*left + $LEFT_RATIO*right
 switch(FloatUtil.compare(sortedArray[center], value, tol)) {
  case 1 :
   return $gsearch(sortedArray, value, tol, left, center);
  case -1:
   return $gsearch(sortedArray, value, tol, center, right);
  default:
   return center;
 }
}

本文链接:https://assnippets.blogspot.com/2008/01/as3_21.html转载请注明出处。

相关文章：