leetcode二分法

二分法

力扣704题目：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果 target 存在返回下标，否则返回 -1。

你必须编写一个具有O(log n)时间复杂度的算法。

讲解：

有序整型数组，去找到一个目标值，就可以考虑使用二分法。这里要考虑左闭右闭区间和左闭右开区间。

这里只说一下左闭右闭区间[1,1]

这里的left是可以等于right的，二分法的思路就是每次取中间值mid，然后去和target进行比较，如果当前中间值小于target，那么我们就把mid+1的值赋值给left；反之，那么我们就把mid-1的值赋值给right。

/*** @param {number[]} nums* @param {number} target* @return {number}*/varsearch=function(nums, target){letleft=0;letright=nums.length-1while(nums[left]<=nums[right]){letmid=Math.ceil((left+right)/2);if(nums[mid]<target){left=mid+1}elseif(nums[mid]>target){right=mid-1}else{returnmid}}return-1};