二分查找关键字：排序数组varbinarySearch=(nums,target)=>{letleft=0;letright=nums.length-1while(left<=right){constmid=left+Math.floor((right-left)/2)if(nums[mid]==traget){returnmid}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，则return将为t依次插入数组nums中的下标。假设数组中没有相同的数字。例如输入数组nums为[1,3,6,8]，如果目标值t为3，则输出1；如果t为5，则返回2。varsearchInsert=function(nums,target){letleft=0letright=nums.length-1while(left<=right){让mid=left+Math.floor((right-left)/2)if(nums[mid]>=target){if(mid==0||nums[mid-1]arr[mid-1]&&arr[mid]>arr[mid+1]){returnmid}elseif(arr[mid]>arr[mid+1]){right=mid;}else{左=中+1;}};returnmid}排序数组中只出现一次的数在一个排序数组中，除了一个数只出现一次外，其他数都出现两次，请找出唯一只出现一次的数。例如，在数组[1,1,2,2,3,4,4,5,5]中，数字3只出现一次。/***@param{number[]}nums*@return{number}*/varsingleNonDuplicate=function(nums){letlow=0,high=nums.length-1;while(low{让low=0,high=pre.长度-1;while(lown，则m为n的平方根。如果m2≤n且(m+1)2≤n，则n的平方根大于m，接下来搜索m+1到n的范围。如果m2>n，则n的平方根小于m，接下来搜索1到m-1的范围。然后在相应的区间重复这个过程，一直取区间中间的m，计算m2和(m+1)2并与n比较，直到找到满足m2≤n和(m+1)2>纳米。/***@param{number}x*@return{number}*/varmySqrt=function(x){letleft=1letright=xwhile(left<=right){constmid=left+Math.floor((右-左)/2)if(mid*mid<=x){if((mid+1)*(mid+1)>x){returnmid}else{left=mid+1}}else{右=中-1}}返回0};不妨使用本机API/***@param{number}x*@return{number}*/varmySqrt=function(x){returnMath.floor(Math.sqrt(x))};狒狒吃香蕉题目：狒狒非常喜欢吃香蕉。有一天它找到了n堆香蕉，第i堆有piles[i]根香蕉。看门人只是走开了，直到H小时后才会回来。狒狒喜欢慢慢咀嚼香蕉，但又想在守卫回来之前吃完所有的香蕉。狒狒每小时至少应该吃多少根香蕉？如果狒狒决定每小时吃k根香蕉，而它正在吃的某一堆剩余香蕉数小于k，那么它只会吃完这堆香蕉，并在接下来的一个小时内开始吃另一堆香蕉。/***@param{number[]}piles*@param{number}h*@return{number}*/varminEatingSpeed=function(piles,h){vargetHours=function(piles,speed){lethours=0for(letpileofpiles){小时+=Math.ceil(pile/speed)}returnhours}letmax=0;对于（让一堆堆）{max=Math。max(max,pile)}letleft=1;letright=maxwhile(left<=right){letmid=left+Math.floor((右-左)/2)lethour=getHours(piles,mid)if(hour<=h){if(mid==1||getHours(piles,mid-1)>h){returnmid}右=中-1}其他{左=中+1}}};Summary介绍了二分查找算法。如果需要在有序数组中查找一个数，可以使用二分查找算法来优化查找效率。二分查找算法的基本思想是在查找范围内选择中间的数。如果中间的数字正好符合要求，那么就找到了目标数字。如果中间数不符合要求，则比较中间数和目标数的大小，据此判断下一轮搜索的范围是当前搜索范围的前半部分还是后半部分。由于每轮搜索将搜索范围缩小一半，如果排序后的数组长度为n，则二分查找算法的时间复杂度为O(logn)。二分查找除了可以在排序的数组中查找一个数外，还可以实现在一个取值范围内进行快速查找。可以先根据值的最小值和最大值来确定搜索范围，然后按照二分查找的思想尝试取值范围的中间值。如果这个中间值不令人满意，请尝试值范围的前半部分或后半部分。
