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

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

Class : advancedflex.utils.FloatArrayUtil

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


public static function bsearch(sortedArray:Array, value:Number, tol:Number = 1e-12):int {
 if(!sortedArray) {
  throw new ArgumentError("Param: must not be null.");
 }
 return $bsearch(sortedArray, value, tol, 0, sortedArray.length-1);
}
/**
 * @private
 * 使用二分查找法来搜索数组的元素。
 * 
 * @param sortedArray 排成升序(从小到大)的数组。
 * @param value 要查找的值。
 * @param tol 浮点小数的计算误差。
 * @param left 查找的最左边。
 * @param right 查找的最右边。
 * @return 元素的下标。如果没有，则返回 -1。
 */
private static function $bsearch(
 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 = (left+right)/2;
 switch(FloatUtil.compare(sortedArray[center], value, tol)) {
  case 1 :
   return $bsearch(sortedArray, value, tol, left, center);
  case -1:
   return $bsearch(sortedArray, value, tol, center, right);
  default:
   return center;
 }
}

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

相关文章：