René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"腾讯：简述二分查找算法与时间复杂度，并实现一个二分查找算法","articleBody":"二分查找也称折半查找算法，它是一种简单易懂的快速查找算法。例如我随机写0-100之间的一个数字，让你猜我写的是什么？你每猜一次，我就会告诉你猜的大了还是小了，直到猜中为止。\r\n\r\n该算法要求待查找的数组已排序，实现步骤如下：\r\n\r\n- 选择数组中的中间数\r\n- 查找数与中间数对比，比中间数低，则去中间数左边的子数组中寻找；比中间数高，则去中间数右边的子数组中寻找；相等则返回查找成功\r\n- 重复上一步，知道查找成功或失败\r\n\r\n```js\r\nfunction binarySearch(items, item) {\r\n    var low = 0,\r\n        high = items.length - 1,\r\n        mid, elem\r\n    while(low \u003c= high) {\r\n        mid = Math.floor((low+high)/2)\r\n        elem = items[mid]\r\n        if(elem \u003c item) {\r\n            low = mid + 1\r\n        } else if(elem \u003e item) {\r\n            high = mid - 1\r\n        } else {\r\n            return mid\r\n        }\r\n    }\r\n    return -1\r\n}\r\n\r\n// 测试\r\nvar arr = [2,3,1,4]\r\n// 快排\r\nquickSort(arr)\r\n\r\nbinarySearch(arr, 3)\r\n// 2\r\n\r\nbinarySearch(arr, 5)\r\n// -1\r\n```\r\n\r\n测试成功\r\n\r\n**二分查找易错点：**\r\n\r\n- 循环退出条件是`low \u003c= high` ，注意是 `\u003c=`\r\n- `mid` 的取值是 `Math.floor((low+high)/2)` \r\n- `low` `high` 每次更新的时候，`low = mid + 1` `high = mid - 1`\r\n\r\n**二分查找局限性：**\r\n\r\n- 针对的对象是数组结构，因为是通过下标来随机访问元素\r\n- 数组必须有序\r\n- 数组太小不合适，直接使用顺序查找即可\r\n- 数组太长不合适，数组要求连续的内存空间，数组太长不利于存储\r\n\r\n**时间复杂度： O(logn)** \r\n\r\n**空间复杂度：O(1)**\r\n\r\n[leetcode](https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-by-user7746o/)","author":{"url":"https://github.com/sisterAn","@type":"Person","name":"sisterAn"},"datePublished":"2020-07-15T13:33:28.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":1},"url":"https://github.com/83/JavaScript-Algorithms/issues/83"}