[toc]
# 題1、交換兩個數的實現？
答：
~~~
let a = 1
let b = 2
寫法一、使用中間變量
let tmp = a
a = b
b = tmp
寫法二、數組賦值
[a,b] = [b,a]
~~~
# 題1、5分鐘之內寫出冒泡排序法？
答：思路：雙層循環，兩兩比較，交換。
最壞時間復雜度：O(n^2)
~~~
let arr = [3,5,3,1,3,4,5,6,4,3,28,9,7,4,3]
// 控制比較的次數
for(let i=0; i<arr.length; i++) {
for(let j=0; j<arr.length-1; j++) {
// 前一個和后一個比較
if(arr[j] > arr[j+1]) {
// 交換
[arr[j], arr[j+1]] = [arr[j+1], arr[j]]
}
}
}
~~~
# 題2、5分鐘之內寫出折半查找法？
答：前提：只能對已經 `排好序` 的數據使用折半查找法。
思路：每次和中間的元素查找，如果查找的元素比它大，就向右查找中間的，如果小就向左查找中間的。
時間復雜度：O(logn)
折半查找法代碼
~~~
// 參數一、有序數組
// 參數二、要查找的數字
// 參數三、開始的下標
// 參數四、結束的下標
function halfSearch(arr, key, left, right) {
let mid // 中間位置的坐標
while(right>left) {
// 計算中間元素的下標
mid = Math.floor((left + right ) / 2)
// 如果找到了就直接返回下標
if(key == arr[mid]) {
return mid
} else if(key < arr[mid]) {
// 右邊界變為中間元素-1
right = mid-1
} else if(key > arr[mid]) {
left = mid+1
}
}
// 沒找到
return -1
}
let arr = [1, 4, 7, 8, 12, 34, 66, 212, 67787, 324345]
console.log( halfSearch(arr, 67787, 0, arr.length-1) )
~~~
