如果覺得前端就是畫頁面 那么文章就不用看了 現在的崗位而言 對應前端的要求越來越高 代碼質量也越高 性能要求也越高
先來一個入門基本的演算法 二分查找 所謂的演算法都不是直接使用關鍵字indexOf findIncludes之類的 都是原生回圈來實作
二分 就是一拆為2 比如一個集合
let list = [1,2,3,4,5,6,7]二分就是在中間拆開變成兩個陣列
list1=[1,2,3,4]
list2 =[5,6,7]二分用在哪些地方 主要有有序陣列的查找
但是說 list= [1.....10] 可能肉眼就知道
但是如果list = [1000,20000] 要找查找某個數位置 就觀察不出來了
更甚至 list = 一千人的電話號碼 要查找某一個
二分不是絕對的性能優秀 所有的優秀的 都是對比的 現在有一個集合放1到10 要找9的的位置
普通的回圈要找9次 二分找幾次呢
let list = [1,2,3,4,5,6,7,8,9,10]
第一次中間數 5,6都可以 目標數9
假設:middle =5
target=9
9>5 下次查找的區間 就用二分的后者 [5,6,7,8,9,10]
接著middle = 7
target = 9
9>7 下次查找的區間 就繼續二分為 [7,8,9,10]
繼續 middle=8
target=9
9>8 下次查找的區間 [8,9,10]
繼續 middle = 9
target= 9
這樣就找到9的位置
二分的特點 不管多長 都是折疊查找 查找的次數比較穩定長度為8的集合 最多3次 就能找到數 log 8=2 就是 =8
同理 16個數 最多需要幾次 2 ? = 16 結果是4 最多查找四次 log16= 4
var list = [1,2,3,4,5,6,7,8,9,10];
function search(list,item){
count =1;//計數出現的次數
start = 0;
end = list.length-1;
while(start<=end){
middle =Math.floor((start+end)/2); //取中間下標
console.log(middle);
guess = list[middle];
if(guess==item){
return middle; //回傳位置
}
if(guess>item){
end = middle;
}else{
start = middle+1
}
count++;
}
return "查不到";
}
let result = search(list,4);
測驗效果
不管開頭還是結尾 還是中間 都穩定在 4次之前解決戰斗
同理 100個數 找一個數 最多7次 40億個數 找32次
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/232667.html
標籤：其他
下一篇：【ML】Naive Bayes