高頻算法：二分搜索

第一步：對數(shù)組進(jìn)行排序

第二步：對排序后的數(shù)組查找中間值

如果查找的元素比中間的值小就返回左側(cè)的數(shù)組，

如果查找的元素比中間的值大就返回右側(cè)的數(shù)組

如果找不到就遞歸再繼續(xù)找，返回左側(cè)和右側(cè)的數(shù)組

在此之前一定要先排序，再查找。

先創(chuàng)建一個(gè)函數(shù)，里面?zhèn)魅?個(gè)參數(shù)，第一個(gè)是要查找的元素find，第二個(gè)是這個(gè)數(shù)組arr，第三個(gè)是數(shù)組中開始的索引start，第四個(gè)是數(shù)組中結(jié)束的索引end。

開始的索引減去結(jié)束的索引除以2就是中間值的索引

第一次開始(start)的索引一定是0，結(jié)束(end)的索引是length-1

如果不傳start=start||0;end=end||arr.length-1

要有start和end的原因，是因?yàn)橐脕碚抑虚g的索引值

?

如果傳入的是空數(shù)組就要先判斷：如果是空數(shù)組就返回-1，表示沒有查找到位置。

查找時(shí)有幾個(gè)特殊情況：

1、如果剛開始查找的值就是要找的值就直接返回start

???if (arr[start] === find) {

????????????????????return start

????????????????}

2、如果最后查找的值就是要找的值就直接返回end

?if (arr[end] === find) {

????????????????????return end

????????????????}

如果查找中間值: 公式：最后值的索引-開始值的索引/2+開始的索引

打個(gè)比方：end為y????start:為x

那么就是（y-x）/2+x?，分解一下就是y/2-x/2+x

而y/2-x/2+x就是(y+x)/2

?

而計(jì)算的值需要使用Math.ceil取整，因?yàn)橛?jì)算的結(jié)果可能不是整數(shù)

(Math.ceil0“向上取整”，即小數(shù)部分直接舍去，并向正數(shù)部分進(jìn)1)

?let mid = Math.ceil((end + start) / 2)

?

3、如果查找的值就是中間值直接返回中間的mid

??if (arr[mid] === find) {

????????????????????return mid

????????????????}

?

?

?

?

4、如果查找的值比中間的值小就重新調(diào)用函數(shù)，而傳入的參數(shù)就是find，arr,start,mid-1

5、如果查找的值比中間的值大就重新調(diào)用函數(shù)，而傳入的參數(shù)就是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）：如果查找的值比最小的值小，比最大的值大的話就會出現(xiàn)一直遞歸查找，所以就需要加上判斷條件查找的值大于等于最小的值和小于等于最大的值。

?if (start <= end && find >= arr[start] && find <= arr[end])

?

完整代碼：

??<script>

????????// 排序

????????function quickSort(arr) {

????????????const { length } = arr

????????????if (length < 2) {

????????????????return arr

????????????}

????????????// 基準(zhǔn)

????????????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

????????????// 調(diào)用排序

????????????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>

?