千锋教育web前端高频面试题视频教程，kerwin大话前端面试秘籍（附答案）
高频算法：二分搜索
第一步：对数组进行排序
第二步：对排序后的数组查找中间值
如果查找的元素比中间的值小就返回左侧的数组，
如果查找的元素比中间的值大就返回右侧的数组
如果找不到就递归再继续找，返回左侧和右侧的数组
在此之前一定要先排序，再查找。
先创建一个函数，里面传入4个参数，第一个是要查找的元素find，第二个是这个数组arr，第三个是数组中开始的索引start，第四个是数组中结束的索引end。
开始的索引减去结束的索引除以2就是中间值的索引
第一次开始(start)的索引一定是0，结束(end)的索引是length-1
如果不传start=start||0;end=end||arr.length-1
要有start和end的原因，是因为要用来找中间的索引值
如果传入的是空数组就要先判断：如果是空数组就返回-1，表示没有查找到位置。
查找时有几个特殊情况：
1、如果刚开始查找的值就是要找的值就直接返回start
if (arr[start] === find) {
return start
}
2、如果最后查找的值就是要找的值就直接返回end
if (arr[end] === find) {
return end
}
如果查找中间值: 公式：最后值的索引-开始值的索引/2+开始的索引
打个比方：end为y start:为x
那么就是（y-x）/2+x ，分解一下就是y/2-x/2+x
而y/2-x/2+x就是(y+x)/2
而计算的值需要使用Math.ceil取整，因为计算的结果可能不是整数
(Math.ceil0“向上取整”，即小数部分直接舍去，并向正数部分进1)
let mid = Math.ceil((end + start) / 2)
3、如果查找的值就是中间值直接返回中间的mid
if (arr[mid] === find) {
return mid
}
4、如果查找的值比中间的值小就重新调用函数，而传入的参数就是find，arr,start,mid-1
5、如果查找的值比中间的值大就重新调用函数，而传入的参数就是find,arr,mid+1,end
else if (arr[mid] > find) {
return binarySearch(find, arr, start, mid - 1)
} else {
return binarySearch(find, arr, mid + 1, end)
}
6、在这里还有一种情况（比如传入的是0）：如果查找的值比最小的值小，比最大的值大的话就会出现一直递归查找，所以就需要加上判断条件查找的值大于等于最小的值和小于等于最大的值。
if (start <= end && find >= arr[start] && find <= arr[end])
完整代码：
<script>
// 排序
function quickSort(arr) {
const { length } = arr
if (length < 2) {
return arr
}
// 基准
let base = arr[0]
let minArr = arr.slice(1).filter(item => item <= base)
let maxArr = arr.slice(1).filter(item => item > base)
return quickSort(minArr).concat(base).concat(quickSort(maxArr))
}
// 二分搜索法
function binarySearch(find, arr, start, end) {
start = start || 0
end = end || arr.length - 1
// 调用排序
arr = quickSort(arr)
console.log(arr)
if (start <= end && find >= arr[start] && find <= arr[end]) {
if (arr[start] === find) {
return start
}
if (arr[end] === find) {
return end
}
let mid = Math.ceil((end + start) / 2)
if (arr[mid] === find) {
return mid
} else if (arr[mid] > find) {
return binarySearch(find, arr, start, mid - 1)
} else {
return binarySearch(find, arr, mid + 1, end)
}
}
return -1
}
binarySearch(2, [2, 1, 8, 6, 9, 23,11])
</script>
