二分查找

二分查找是一种非常简单易懂的疾速查找算法，生存中到处可见。比如说，咱们当初来做一个猜字游戏。我随机写一个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};留神点： ...