Day16:[搜寻演算法]Binary search - 二分搜寻法

利用将资料切一半的方式来做搜寻，举例来说，如果要从数字1–100猜终极密码，如果采用线性搜寻法就是一个一个问?是1吗?是2吗?…依序猜下去，很不幸的数字刚好是99就需要猜99次，但如果用二分搜寻法就会是先判断数字是否大於50 ，如果是的话那是否大於75 ，依此类推每次都用对半砍的方式缩小范围，最後只需要猜七次就能猜出终极密码。

每次都将搜寻范围缩减1/2

使用二分搜寻法的前提必须是先排序过

假设目前有个阵列:[10, 21, 34, 50, 66,79, 82, 97]，要找出阵列中是否有79这个数字，有的话就回传79在哪个index

这边运用到双指针的概念来解题(left, right)，关於双指针的说明可以参考这篇文章， 这里可以先想像有两个指针会不断往中间靠拢，进而缩短搜寻区间。

实作的概念为:

1. 先在阵列取一个中间数的index，公式为 Math.floor((left+right)/2)，0+7除以2无条件舍去後拿到3，这边用middle标示为中间数。
   
   上方黄色小字为index2

2. 这时拿目标数79去跟中间数50比较，目标数79比较大，代表中间数的左边那堆数字都不可能是我们要找的答案(都太小了)，所以我们要调整一下搜寻范围，将left指针移动到middle+1的位置。

为甚麽要middle+1?因为已经知道middle不是答案，搜寻范围就可以排除middle了

3. 重新计算中间数，(4+7)/2无条件舍去算出5，而在index 5的数字79就是我们要找的数字。
   

用js实作二分搜寻法

时间复杂度

• 在最差的情况下， 时间复杂度是O(log n)
• 在最佳的情况下 ， 时间复杂度是O(1)
• 在平均情况下，时间复杂度为 O(log n)