二分查找

二分查找是一种非常简单易懂的疾速查找算法，生存中到处可见。比如说，咱们当初来做一个猜字游戏。我随机写一个0到99之间的数字，而后你来猜我写的是什么。猜的过程中，你每猜一次，我就会通知你猜的大了还是小了，直到猜中为止。你来想想，如何疾速猜中我写的数字呢？无处不在的二分思维二分查找是一种非常简单易懂的疾速查找算法，生存中到处可见。比如说，咱们当初来做一个猜字游戏。我随机写一个0到99之间的数字，而后你来猜我写的是什么。猜的过程中，你每猜一次，我就会通知你猜的大了还是小了，直到猜中为止。你来想想，如何疾速猜中我写的数字呢？ 假如我写的数字是23，你能够依照上面的步骤来试一试。（如果猜想范畴的数字有偶数个，两头数有两个，就抉择较小的那个。） 7次就猜出来了，是不是很快？这个例子用的就是二分思维，依照这个思维，即使我让你猜的是0到999的数字，最多也只有10次就能猜中。不信的话，你能够试一试。 看懂这两个例子，你当初对二分的思维应该把握得妥妥的了。我这里略微总结升华一下， 二分查找针对的是一个有序的数据汇合，查找思维有点相似分治思维。每次都通过跟区间的两头元素对比，将待查找的区间放大为之前的一半，直到找到要查找的元素，或者区间被放大为0。 二分查找惊人的查找速度二分查找是一种十分高效的查找算法，高效到什么水平呢？咱们来剖析一下它的工夫复杂度。咱们假如数据大小是n，每次查找后数据都会放大为原来的一半，也就是会除以2。最坏状况下，直到查找区间被放大为空，才进行。能够看进去，这是一个等比数列。其中n/2k=1时，k的值就是总共放大的次数。而每一次放大操作只波及两个数据的大小比拟，所以，通过了k次区间放大操作，工夫复杂度就是O(k)。通过n/2k=1，咱们能够求得k=log2n，所以工夫复杂度就是O(logn)。 残缺内容请点击下方链接查看：“二分”带来“非常”快感——二分思维的神秘解析 版权申明：本文内容由阿里云实名注册用户自发奉献，版权归原作者所有，阿里云开发者社区不领有其著作权，亦不承当相应法律责任。具体规定请查看《阿里云开发者社区用户服务协定》和《阿里云开发者社区知识产权爱护指引》。如果您发现本社区中有涉嫌剽窃的内容，填写侵权投诉表单进行举报，一经查实，本社区将立即删除涉嫌侵权内容。

1. 整体阐明二分查找是根本的、常见的算法，大家徒手写应该不成问题。面试中经常出现,特地是面试官想给你送分的时候。但大多数时候大家的二分查找写法其实在面试官看来仅仅是及格。大家可能会想，二分查找能玩出什么花色来？明天，咱们一起来看。本文常识要求：会看图，会识字。 2. 最简略的二分查找话不多说，间接看leetcode 原题。leetcode704 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜寻 nums 中的 target，如果目标值存在返回下标，否则返回 -1。示例 1:输出: nums = [-1,0,3,5,9,12], target = 9输入: 4解释: 9 呈现在 nums 中并且下标为 4示例 2:输出: nums = [-1,0,3,5,9,12], target = 2输入: -1解释: 2 不存在 nums 中因而返回 -1提醒：n 将在 [1, 10000]之间。nums 的每个元素都将在 [-9999, 9999]之间 起源：力扣（LeetCode）链接：https://leetcode.cn/problems/binary-search 上面是最常见的实现版本，咱们后续称之为版本A. func searchA(nums []int, target int) int { lo, hi := 0, len(nums) // 在左闭右开区间[lo, hi) 查找target var mid int var midVal int for lo < hi { // 最初退出时，[lo,hi）区间为空 mid = (lo + hi) / 2 // 两头索引 midVal = nums[mid] if midVal == target { return mid } else if target < midVal { hi = mid } else { // midVal < target lo = lo + 1 } } return -1}3. 这么简略的算法还能优化吗？该算法工夫复杂度为O(Nlogn), n为数组长度，N为系数。咱们的指标是：是否让N 小一些。咱们看下面的版本A实现，发现每次循环中，通过 nums[mid] ，通过2次比拟，将数组分为三局部。如下图所示。其实，咱们能够将nums[mid] 和nums[mid+1, hi) 合并为一个区间，这个区间的元素满足 >= target。这样做的目标是将比拟次数优化为1.退出区间时，hi = lo+1, 区间[lo,hi)仅有一个元素(可能会对这个优化的意义产生疑难。如果咱们的数组不是整数，而是长字符串呢？)1次比拟，划分为2个区间示意图。此时算法实现如下，咱们称之为版本B。 ...

题目 合并有序数组间接返回中位数 func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { var nums3 []int var a,b int //合并数组 for a<len(nums1)&&b<len(nums2){ if nums1[a]<nums2[b]{ nums3=append(nums3,nums1[a]) a++ }else { nums3=append(nums3,nums2[b]) b++ } } if a==len(nums1){ nums3=append(nums3,nums2[b:len(nums2)]...) }else{ nums3=append(nums3,nums1[a:len(nums1)]...) } //取中位数 if len(nums3)%2==1{ return float64(nums3[len(nums3)/2]) }else{ return (float64(nums3[len(nums3)/2-1])+float64(nums3[len(nums3)/2]))/2 }}复杂度工夫O（m+n）空间O（1） 合并数组应用了太多工夫，将其优化为log因为两个数组都为有序数组，在指标数字之前的数都必然小于它，这就容许咱们进行疾速的排除定义i，j两个指针，每次排除k/2个必然不是中位数的数，并将指针前移直到非凡状况找到第k个数 func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { //find (m+n+1)/2 and (m+n+2)/2 m:=len(nums1) n:=len(nums2) res1:=getKthElement(nums1,nums2,(m+n+2)/2) res2:=getKthElement(nums1,nums2,(m+n+1)/2) return (float64(res1)+float64(res2))/2}func getKthElement(nums1 []int, nums2 []int, k int)int{ var index1,index2 int for { //如果一个数组已被排查完，间接返回另一个数组的第k个元素 if index1 == len(nums1) { return nums2[index2 + k - 1] } if index2 == len(nums2) { return nums1[index1 + k - 1] } //如果要找最小的元素，则只有两种可能性，间接比拟找到后果 if k == 1 { return min(nums1[index1], nums2[index2]) } //更新排除的数k/2，实现比拟，排除小于k的数，k值减小 half := k/2 newIndex1 := min(index1 + half, len(nums1)) - 1 newIndex2 := min(index2 + half, len(nums2)) - 1 pivot1, pivot2 := nums1[newIndex1], nums2[newIndex2] if pivot1 <= pivot2 { k -= (newIndex1 - index1 + 1) index1 = newIndex1 + 1 } else { k -= (newIndex2 - index2 + 1) index2 = newIndex2 + 1 } }}func min(x, y int) int { if x < y { return x } return y} ...

二分查找关键词： 排序数组 var binarySearch = (nums, target) => { let left = 0; let right = nums.length -1 while(left <= right) { const mid = left + Math.floor((right - left)/2) if(nums[mid] == traget) { return mid } if (nums[mid] > target) { right = mid - 1 } else { left = mid + 1 } } return -1}二分查找算法每次将查找范畴缩小一半，因而对于一个长度为n的数组可能须要O（logn）次查找，每次查找只须要比拟以后查找范畴的两头数字和指标数字，在O（1）的工夫能够实现，因而二分查找算法的工夫复杂度是O（logn）。 数组既可能是整体排序的，也可能是分段排序的，但一旦题目是对于排序数组并且还有查找操作，那么二分查找算法总是值得尝试的。在排序数组中二分查找查找插入地位输出一个排序的整数数组nums和一个目标值t，如果数组nums中蕴含t，则返回t在数组中的下标；如果数组nums中不蕴含t，则返回将t按程序插入数组nums中的下标。假如数组中没有雷同的数字。例如，输出数组nums为[1，3，6，8]，如果目标值t为3，则输入1；如果t为5，则返回2。var searchInsert = function(nums, target) { let left = 0 let right = nums.length - 1 while(left <= right) { let mid = left + Math.floor((right - left) / 2) if(nums[mid] >= target) { if(mid == 0 || nums[mid - 1] < target) { return mid } right = mid - 1 } else { left = mid + 1 } } return nums.length}山峰数组的顶部在一个长度大于或等于3的数组中，任意相邻的两个数字都不相等。该数组的前若干数字是递增的，之后的数字是递加的，因而它的值看起来像一座山峰。请找出山峰顶部，即数组中最大值的地位。例如，在数组[1，3，5，4，2]中，最大值是5，输入它在数组中的下标2。不难想到直观的解法来解决这个题目，即逐个扫描整个数组，通过比拟就能找出数组中的最大值。显然，这种解法的工夫复杂度是O（n）。 ...

原文出处 二分查找算法+代码(通俗易懂简洁简要)欢送关注我知乎帐号进击的steve 二分查找是一个能够把单值查找时间复杂度从O(n)降到O(logn)的算法。 二分查找的前提是数组有序(依照从小到大或从大到小的顺序排列) 有两种办法能够实现：递归和循环 为了节约寄存函数调用的栈，个别倡议应用循环 def binarysearch(nums, target): # 循环实现 工夫复杂度O(logn) low = 0 high = len(nums)-1 while low <= high: mid = (low + high) // 2 guess = nums[mid] if guess == target: return mid elif guess < target: low = mid + 1 else: high = mid - 1 return -1如果nums=[1,2,7,7,7,7,7,9], target=7, 查找最左侧的7怎么办? def binarysearch2(self, nums, target): # 工夫复杂度O(logn) left, right = 0, len(nums)-1 while left <= right: mid = (left + right) // 2 if nums[mid] == target: if mid == 0 or nums[mid-1] != target: return mid else: right = mid - 1 elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1github代码出处：https://github.com/stevezkw19... ...

对于二分查找的题型一般的二分 LC704 二分查找 简略LC34 在排序数组中查找元素的第一个和最初一个地位 中等变体：旋转数组 LC153 寻找旋转排序数组的最小值 中等LC33 搜寻旋转排序数组 中等二分通用技巧最罕用最根底的二分查找，接管一个数组，和一个target目标值，要寻找到这个指标，返回该指标的下标。找不到就返回-1。间接对应LC704的答案 function search(nums: number[], target: number): number { let left: number = 0, right: number = nums.length - 1 while (left <= right) { let mid: number = Math.floor(left + (right - left) / 2) if (nums[mid] < target){ left = mid + 1 } else if (nums[mid] > target){ right = mid - 1 } else if (nums[mid] === target){ return mid } } return -1};留神点： ...

4:FindMedianSortedArraysThere are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. Example 1: nums1 = [1, 3]nums2 = [2]The median is 2.0Example 2: nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5一、按时间复杂度O（m+n）解先来解释一下什么是中位数如下：[3，4，5] , 那么这组数的中位数就是4[3，4，5，6] , 那么这组数的中位数就是 （4+5）／2 = 4.5开始没有注意到时间复杂度，但按照O（m+n）解，也花了我不少时间，可能是很久没有接触算法的缘故。 ...

二分查找（英语：binary search），也称折半搜索（英语：half-interval search）对数搜索（英语：logarithmic search，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 适合的场景： Sorted（单调递增或者递减）Bounded （存在上下界，因为要一分为二的进行查找）Accessible by index（能够通过索引访问）时间复杂度： O(logN)空间复杂度: O(N) 使用常数空间，无论任何大小的输入数据，算法使用的空间都是一样的适用的数据结构： 数组，因为在内存中时连续的适合使用二分查找。但是链表不适合，因为链表坐标不是固定的，访问a[2]需要先从a[0]的后继节点找到a[1]再通过a[1]的后继节点才能访问到a[2]。 步骤： 初始状态left、right 分别指向数组的头和尾。通过(left + right) /2 得到中间位置mid，访问数组中mid位置的元素。判断其与查找目标的大小关系，相等则程序返回，比目标小则挪动left指针到mid + 1；比目标大则挪动right指针到mid - 1重复上面步骤2 ～ 3直到找到目标元素或者程序退出。代码实现: <?php$list = [1, 2, 5, 6, 8, 9, 12, 15, 23, 32, 56, 67, 73, 85];function bioSearch($list, $target){ $left = 0; $right = count($list) - 1; while ($left <= $right) { $mid = ($left + $right) / 2; if ($list[$mid] == $target) { return true; } else if ($list[$mid] < $target) { $left = $mid + 1; continue; } else { $right = $mid - 1; continue; } } return false;}

虽然二分法很简单，但是之前并没有对其有过太多的注意，只是把它当成一个查找元素的方法来应用，但是随着后面做题的深入，发现二分法也有很多讲究，所以这里做一个总结归纳一下；一、二分法的基础概念：二分法研究的序列可以分为重复或者非重复序列，其序列要求都是递增有序的；对于非重复序列，我们可以很简单的给出相应的推理和逻辑；例如，我们如果要在一个严格递增序列中查找给定的x，就可以有以下代码：int binarySearch(int A[],int left,int right,int x){ int mid; while(left<=right){ mid=(left+right)/2; if(A[mid]==x) return mid; else if(A[mid]>x){ right=mid-1; }else{ left=mid+1; } } return -1;}注意两点：1.判定条件left<=right,有的情况下写成left<right，这个需要视情况而定；2.当left和right达到一定程度的时候，如果简单相加计算mid的时候，可能会导致溢出，所以往往比较保险的办法就是：mid=left+(right-left)/2这样就可以很好的避免溢出，从而保证能够进行mid的计算；上述针对的是递增非重复序列，如果重复序列，我们又该作何思考？例如示例中给出的问题，如果给出一个重复的递增序列A，我们需要求出第一个大于等于x的位置L以及第一个大于x的元素的位置R；这是两个小问题，首先先进行第一个小问题的求解：找出第一个大于等于x的位置L；其实对于这个问题，前提就已经默认了，必有L存在，所以判定条件就会发生相应的变化；int lower_bound(int A[],int left,int right,int x){ int mid; while(left<right){ mid=(left+right)/2; if(A[mid]>=x){ right=mid-1; }else{ left=mid+1; } } return left;}这里我们可以看出变了两个条件，第一个是left<right，第二个是A[mid]>=x；对于第一个条件的改变，我们可以理解为把符合条件的元素夹出来，当循环终止的时候，必有left=right,此时两个索引指向同一个元素，该元素就是我们在寻找的元素；而对于第二个条件的改变，则是由于题目性质决定的；如果中间点大于等于x，则我们可以认为要寻找的第一个x在mid的左边，所以right=mid。即使在等于条件下，由于right=mid，所以还是可以保证要寻找的数在[left,right]区间内；这一点和之前的mid+1和mid-1完全不同，其根本原因是序列内元素是否唯一；如果难以判别使用哪种方法，则每次及逆行mid迭代的时候，一定要试一试边界是否能够像预期那样包括进行需要寻找的元素；第二个自问题就是求序列中第一个大于x的位置;对于这个问题，我们仍然需要关注的是判定条件;代码如下：int upper_bound(int A[],int left,int right,int x){ int mid; while(left<right){ mid=(left+right)/2; if(A[mid]>x){ right=mid; }else{ left=mid+1; } } return left;}对于个算法，同样的我们需要left==right来将符合的值夹出来；当A[mid]>x时，由于我们寻找的时大于x的值，此时该值必在mid的左边，同样的，如果mid就是大于x的值，也应该包括进去，所以此时，right=mid;当A[mid]<=x时，由于我们寻找的是一个大于x的值，所以mid不必包括进去，left=mid+1;总的来说，上述推举的方法，都在解决一个核心问题：在该序列中，找到第一个符合该条件的值；二、二分法的主要应用：1.利用二分法求某数字的近似值：这个问题其实很经典，自己以前碰到过几次；例如：求解根号2的近似值，要求精度在10^-5；这个问题就可以利用该方法进行计算；首先我们需要构建目标函数F(x)=x^2，从而转换成1~2区间内的实数计算；设置边界left=1，right=2，来利用函数进行逼近；代码如下：const double eps=1e-5;double f(double x){ return xx;}int binarySearch(){ double left=1; double right=2; double mid; while(right-left>1e-5){ mid=(right+left)/2; if(f(mid)>2){ right=mid; }else{ left=mid; } } return mid;}2.快速幂：快速幂就是给出三个整数a,b,m,求得a^b%m；这个问题也可以采用二分思想来进行递归计算；若b是奇数：a^b=aa^(b-1)若b是偶数：a^b=a^(b/2)a^(b/2);代码如下：long long binarypow(long long a,long long b,long long m){ if(b==0) return 1; if(b%2==1) return abinarypow(a,b-1,m)%m; else{ long long mul=binarypow(a,b/2,m); return mul*mul%m; }}注意上述的mul，不要单纯计算两次a^(b/2),而使用mul，这样可以适当的介绍时间复杂度； ...

题目Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.Example 1:Input: [1,1,2,3,3,4,4,8,8]Output: 2Example 2:Input: [3,3,7,7,10,11,11]Output: 10Note: Your solution should run in O(log n) time and O(1) space.题目地址讲解二分查找，包含一个数的一边个数一定是奇数个。java代码class Solution { public int singleNonDuplicate(int[] nums) { return binarySearch(nums, 0, nums.length-1); } private int binarySearch(int[] nums, int left, int right){ if(left==right){ return nums[left]; } int mid = (left+right)/2; if(nums[mid-1]==nums[mid]){ if((right-mid)%2==1){ return binarySearch(nums, mid+1, right); }else{ return binarySearch(nums, left, mid-2); } }else if(nums[mid+1]==nums[mid]){ if((mid-left)%2==1){ return binarySearch(nums, left, mid-1); }else{ return binarySearch(nums, mid+2, right); } }else{ return nums[mid]; } }} ...