快捷導(dǎo)航

JavaScript實(shí)現(xiàn)二分查找實(shí)例代碼

更新時(shí)間：2017年02月22日 10:00:34 作者：albert_knag

二分查找的前提為：數(shù)組、有序。這篇文章主要介紹了JavaScript實(shí)現(xiàn)二分查找實(shí)例代碼,需要的朋友可以參考下

二分查找的前提為：數(shù)組、有序。邏輯為：優(yōu)先和數(shù)組的中間元素比較，如果等于中間元素，則直接返回。如果不等于則取半繼續(xù)查找。

/**
 * 二分查找，遞歸實(shí)現(xiàn)。
 * @param target
 * @param arr
 * @param start
 * @param end
 * @returns {*}
 */
function binarySearch(target,arr,start,end) {
  var start  = start || 0;
  var end   = end || arr.length-1;
  var mid = parseInt(start+(end-start)/2);
  if(target==arr[mid]){
    return mid;
  }else if(target>arr[mid]){
    return binarySearch(target,arr,mid+1,end);
  }else{
    return binarySearch(target,arr,start,mid-1);
  }
  return -1;
}
/**
 * 有序的二分查找，返回-1或存在的數(shù)組下標(biāo)。不使用遞歸實(shí)現(xiàn)。
 * @param target
 * @param arr
 * @returns {*}
 */
function binarySearch(target,arr) {
  var start  = 0;
  var end   = arr.length-1;
  while (start<=end){
    var mid = parseInt(start+(end-start)/2);
    if(target==arr[mid]){
      return mid;
    }else if(target>arr[mid]){
      start  = mid+1;
    }else{
      end   = mid-1;
    }
  }
  return -1;
}

寫完有序，自然而然的想到了無序的情況如何使用二分查找呢？馬上想到先使用快排分組，分好組再二分。代碼如下：

/**
 * 無序的二分查找。返回true/false
 * @param target
 * @param arr
 * @returns {boolean}
 */
function binarySearch(target,arr) {
  while (arr.length>0){
    //使用快速排序。以mid為中心劃分大小，左邊小，右邊大。
    var left  = [];
    var right  = [];
    //選擇第一個(gè)元素作為基準(zhǔn)元素(基準(zhǔn)元素可以為任意一個(gè)元素)
    var pivot  = arr[0];
    //由于取了第一個(gè)元素，所以從第二個(gè)元素開始循環(huán)
    for(var i=1;i<arr.length;i++){
      var item = arr[i];
      //大于基準(zhǔn)的放右邊，小于基準(zhǔn)的放左邊
      item>pivot ? right.push(item) : left.push(item);
    }
    //得到經(jīng)過排序的新數(shù)組
    if(target==pivot){
      return true;
    }else if(target>pivot){
      arr   = right;
    }else{
      arr   = left;
    }
  }
  return false;
}

寫完用快速排序?qū)崿F(xiàn)的無序二分查找，仔細(xì)想了一下該算法的時(shí)間復(fù)雜度，發(fā)現(xiàn)還不如直接一個(gè)for循環(huán)來得快

以上所述是小編給大家介紹的JavaScript實(shí)現(xiàn)二分查找實(shí)例代碼，希望對大家有所幫助，如果大家有任何疑問請給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對腳本之家網(wǎng)站的支持！

您可能感興趣的文章: