您好,登錄后才能下訂單哦!
二分查找的前提為:數(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; }
寫(xiě)完有序,自然而然的想到了無(wú)序的情況如何使用二分查找呢?馬上想到先使用快排分組,分好組再二分。代碼如下:
/** * 無(wú)序的二分查找。返回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è)元素開(kāi)始循環(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)過(guò)排序的新數(shù)組 if(target==pivot){ return true; }else if(target>pivot){ arr = right; }else{ arr = left; } } return false; }
寫(xiě)完用快速排序?qū)崿F(xiàn)的無(wú)序二分查找,仔細(xì)想了一下該算法的時(shí)間復(fù)雜度,發(fā)現(xiàn)還不如直接一個(gè)for循環(huán)來(lái)得快
以上所述是小編給大家介紹的JavaScript實(shí)現(xiàn)二分查找實(shí)例代碼,希望對(duì)大家有所幫助,如果大家有任何疑問(wèn)請(qǐng)給我留言,小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)億速云網(wǎng)站的支持!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。