【算法图解-01_二分查找】
二分查找
❍
下面的示例说明了二分查找的工作原理。我随便想一个1～100的数字。你的目标是以最少的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。假设你从1开始依次往上猜，猜测过程会是这样。
这是简单查找，更准确的说法是傻找。每次猜测都只能排除一个数字。如果我想的数字是99， 你得猜99次才能猜到！
下面是一种更佳的猜法。从 50 开始。
小了，但排除了一半的数字！至此，你知道1～50都小了。接下来，你猜75。
大了，那余下的数字又排除了一半！使用二分查找时，你猜测的是中间的数字，从而每次都 将余下的数字排除一半。接下来，你猜63（50和75中间的数字）
这就是二分查找，你学习了第一种算法！每次猜测排除的数字个数如下。
不管我心里想的是哪个数字，你在7次之内都能猜到，因为每次 猜测都将排除很多数字！假设你要在字典中查找一个单词，而该字典包含240 000个单词， 你认为每种查找最多需要多少步？如果要查找的单词位于字典末尾，使用简单查找将需要240 000步。使用二分查找时，每次 排除一半单词，直到最后只剩下一个单词
因此，使用二分查找只需18步——少多了！一般而言，对于包含n个元素的列表，用二分查 找最多需要log2n步（对数是幂运算的逆运算），而简单查找最多需要n步。
仅当列表是有序的时候，二分查找才管用
二分查找C++实现
class Solution {public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]while (left <= right) { // 当left==right，区间[left, right]依然有效，所以用 <=int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (nums[middle] > target) {right = middle - 1; // target 在左区间，所以[left, middle - 1]} else if (nums[middle] < target) {left = middle + 1; // target 在右区间，所以[middle + 1, right]} else { // nums[middle] == targetreturn middle; // 数组中找到目标值，直接返回下标}}// 未找到目标值return -1;}};
leetcode 35. 搜索插入位置 https://leetcode-cn.com/problems/search-insert-position/
class Solution {public:int searchInsert(vector<int>& nums, int target) {int left = 0;int right = nums.size()-1;while(left <= right){int middle = (left + right) / 2;// int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2if (target < nums[middle]){right = middle - 1;}else if (target > nums[middle]){left = middle + 1;}else{return middle;}}// 分别处理如下四种情况// 目标值在数组所有元素之前 [0, -1]// 目标值等于数组中某一个元素 return middle;// 目标值插入数组中的位置 [left, right]，return right + 1// 目标值在数组所有元素之后的情况 [left, right]，return right + 1;}};
leetcode 704.二分查找 https://leetcode-cn.com/problems/binary-search/submissions/
class Solution {public:int search(vector<int>& nums, int target) {int left = 0;int right = nums.size() - 1;while(left <= right){int middle = (left + right) / 2;if(target < nums[middle]){right = middle - 1;}else if(target > nums[middle]){left = middle + 1;}else{return middle;}}return -1;}};
二分查找Python实现
◉
●
◉
点个不要钱的“在看”就好啦！
努力活成自己喜欢的样子~
你期待的都会来到你身边
走过路过不要错过
想攒点奶粉钱