JavaScript实现二分查找实例代码

/**

 * 二分查找，递归实现。

 * @param target

 * @param arr

 * @param start

 * @param end

 * @returns {*}

 */

functionbinarySearch(target,arr,start,end) {

  varstart  = start || 0;

  varend   = end || arr.length-1;

  varmid = parseInt(start+(end-start)/2);

  if(target==arr[mid]){

    returnmid;

  }elseif(target>arr[mid]){

    returnbinarySearch(target,arr,mid+1,end);

  }else{

    returnbinarySearch(target,arr,start,mid-1);

  }

  return-1;

}

/**

 * 有序的二分查找，返回-1或存在的数组下标。不使用递归实现。

 * @param target

 * @param arr

 * @returns {*}

 */

functionbinarySearch(target,arr) {

  varstart  = 0;

  varend   = arr.length-1;

  while(start<=end){

    varmid = parseInt(start+(end-start)/2);

    if(target==arr[mid]){

      returnmid;

    }elseif(target>arr[mid]){

      start  = mid+1;

    }else{

      end   = mid-1;

    }

  }

  return-1;

}

/**

 * 无序的二分查找。返回true/false

 * @param target

 * @param arr

 * @returns {boolean}

 */

functionbinarySearch(target,arr) {

  while(arr.length>0){

    //使用快速排序。以mid为中心划分大小，左边小，右边大。

    varleft  = [];

    varright  = [];

    //选择第一个元素作为基准元素(基准元素可以为任意一个元素)

    varpivot  = arr[0];

    //由于取了第一个元素，所以从第二个元素开始循环

    for(vari=1;i

      varitem = arr[i];

      //大于基准的放右边，小于基准的放左边

      item>pivot ? right.push(item) : left.push(item);

    }

    //得到经过排序的新数组

    if(target==pivot){

      returntrue;

    }elseif(target>pivot){

      arr   = right;

    }else{

      arr   = left;

    }

  }

  returnfalse;

}