力扣每日一题-二分查找类型题目

二分查找的主要情况分成7种情况：

1. 查找对应target位置（返回对应位置，没找到则返回-1）

2. 查找第一个大于或等于target的位置（返回对应位置，没找到则返回-1）

3. 查找第一个大于target的位置（返回对应位置，没找到则返回-1）

4. 查找最后一个小于等于target的位置（返回对应位置，没找到则返回-1）

5. 查找最后一个小于target的位置（返回对应位置，没找到则返回-1）

6. 查找第一个等于target的位置（返回对应位置，没找到则返回-1）

7. 查找最后一个等于target的位置（返回对应位置，没找到则返回-1）

1	1. 查找对应target位置（返回对应位置，没找到则返回-1）

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

1	2. 查找第一个大于或等于target的位置（返回对应位置，没找到则返回-1）

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if nums[mid] >= target:
            high = mid - 1
        elif nums[mid] < target:
            low = mid + 1
    if low <= len(nums)-1:
        return low
    else:
        return -1

1	3. 查找第一个大于target的位置（返回对应位置，没找到则返回-1）

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if nums[mid] > target:
            high = mid - 1
        elif nums[mid] <= target:
            low = mid + 1
    if low <= len(nums)-1:
        return low
    else:
        return -1

1	4. 查找最后一个小于等于target的位置（返回对应位置，没找到则返回-1）

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if nums[mid] <= target:
            low = mid + 1
        elif nums[mid] > target:
            high = mid - 1
        if high >= 0:
       		 return high
        else:
        	return -1

1	5. 查找最后一个小于target的位置（返回对应位置，没找到则返回-1）

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if nums[mid] < target:
            low = mid + 1
        elif nums[mid] >= target:
            high = mid - 1
    if high >= 0:
      	return high
	else:
      	return -1

1	6. 查找第一个等于target的位置（返回对应位置，没找到则返回-1）

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if mid[mid] >= target:
            high = mid - 1
        else:
            low = mid + 1
    if low <= len(nums)-1 and nums[low] == target:
        return low
    else:
        return -1

1	7. 查找最后一个等于target的位置（返回对应位置，没找到则返回-1）

def find(nums,target):
    low = 0
    high = len(nums)-1
    while low <= high:
        mid = low + (high - low)//2
        if nums[mid] <= target:
            low = mid + 1
        else:
            high = mid - 1
    if high >= 0 and nums[high] == target:
        return high
    else:
        return -1

69. x 的平方根

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

题解

最简单的使用函数求平方根最简单不过了，但是一般面试情况下不允许直接用函数求取平方根，所以这里可以用二分查找。

由于 x平方根的整数部分 ans 是满足k*2≤x 的最大 k值，因此我们可以对 k 进行二分查找，从而得到答案。

虽然思路很简单，但是中间的限制条件搞了好久，一定要注意限定条件！！！

对于 x = 8，它的开方是 2.82842…，最后应该返回 2 而不是 3。在循环条件为 l <= h 并且循环退出时，h 总是比 l 小 1，也就是说 h = 2，l = 3，因此最后的返回值应该为 h 而不是 l。

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    // return Math.floor(Math.sqrt(x));    //直接得到结果
    if(x == 0 || x ==1){
        return x;
    }
    var left = 1;
    var right = x;
    while(left <= right){
       var middle = left + ((right-left)>>1);
       if(middle*middle == x){
           return middle;
       }else if(middle*middle > x){
           right = middle-1;
       }else{
           left = middle+1;
       }
    }
    return right;
};

744. 寻找比目标字母大的最小字母

给你一个排序后的字符列表 letters ，列表中只包含小写英文字母。另给出一个目标字母 target，请你寻找在这一有序列表里比目标字母大的最小字母。

在比较时，字母是依序循环出现的。举个例子：

如果目标字母 target = 'z' 并且字符列表为 letters = ['a', 'b']，则答案返回 'a'

示例：

输入:
letters = [“c”, “f”, “j”]
target = “a”
输出: “c”

题解

1.left<right的思路，如果mid处的字母<=target的字母就向右侧去查找，反之向左侧查找，为了找到比target大的最小的字母，所以需要查找到left=right为止，在第一次找到大于target之后就需要向左收缩右边界直到left=right;

var nextGreatestLetter = function(letters, target) {
    let len = letters.length;
    if(len<=1){
        return 0;
    }
    let left = 0,right = len-1;
    while(left<right){
       let mid = Math.floor(left+(right-left)/2);  //不知道为甚什么这里非得加一个向下取整，明明不加也是整数，但不知道为什么
       if(letters[mid] <= target){
           left = mid+1;
       }else{
           right = mid;
       }
    }
    if(letters[left]>target){
        return letters[left];
    }
    return letters[0];

    // var left = 0,
    // right = letters.length - 1,
    // midIndex;
    // while (left < right) {
    //     midIndex = Math.floor(left + (right - left) / 2);
    //     if (letters[midIndex] <= target) {
    //         left = midIndex + 1;
    //     } else {
    //         right = midIndex;
    //     }
    // }
    // if (letters[left] > target) return letters[left];
    // return letters[0];

};

2.按照上面的模板套的，我觉得没有什么问题，但是老是通不过。也用给的例子试了，他得出的用例结果和我算的不同，先记录下来吧。代码如下：

var nextGreatestLetter = function(letters, target) {
    let len = letters.length
    let l = 0, r = len-1;
    while(l<=r){
        let mid = (l+r)/2;                     //这里改成 let mid = Math.floor((l+r)/2)就可以了哈哈哈
        if(letters[mid]>target){
            r = mid-1;
        }else{
            l = mid+1;
        }  
    }
    if (l <=len-1){
        return letters[l];
    }else{
        return letters[0];
    }
}

老提示我其中一个用例错误是（头疼ing）：

后续来了。。。。。终于知道自己为什么思路正确但总是通不过用例了，原因是因为没有给mid求得值向下取整，也就是只需要将let mid = (l+r)/2改为mid = Math.floor((l+r)/2))就行，以后就记住一条规律，求中间值时都加上向下取整函数。

3.暴力求解

1.将target push 进 letters
2.去重
3.sort
4.取出target下标+1的值
5.如果目标不存在则返回 letters[0];否则返回目标

/**
 * @param {character[]} letters
 * @param {character} target
 * @return {character}
 */
var nextGreatestLetter = function(letters, target) {
    letters.push(target)
    letters = [...new Set(letters)]
    letters.sort()
    let d = letters[letters.indexOf(target)+1]
    if(!d) return letters[0]
    else return d
};

540. 有序数组中的单一元素

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1:

输入: [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: [3,3,7,7,10,11,11]
输出: 10

注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

题解

1.利用双指针(相当于还是暴力解法)

设置l和r两个双指针，初始值分别为0和1，如果二者相等则同时加2继续比较，限制条件是l<=数组的长度-1。如果设置r<=数组的长度减1的话，则会溢出。代码如下：

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function(nums) {
    if(nums.length == 1){
        return nums[0];
    }
    let l = 0,r = 1;
    while(l<=nums.length){
        if(nums[l]==nums[r]){
            l+=2;
            r+=2;
        }else{
            return nums[l];
        }
    }
    
};n

时间复杂度：O(n)

空间复杂度：O(1)

2.二分查找算法实现，当时想不出来满足有两个一样的数后的下一步该怎么约束，看了人家的想法才知道。还是得多练习，二分查找算法虽然思路简单，但是在不同的情境下运用还是有一定难度的。代码如下：

var singleNonDuplicate = function(nums) {
  let l=0,r=nums.length-1;
    while(l<=r){
        mid = (l+r)/2;
        if(nums[mid]==nums[mid-1]){
            if((mid)%2 == 0){                    //这里是指包含mid的前一个在内，如果mid前面的数的总数是偶数，就说明肯定这个单独的数在mid的左边。因为mid的左边第一个已经和mid相等了，再有一个单独的数才能凑成偶数的数目。
                 r=mid-2;
            }else{
                l = mid+1
            }
        }else if(nums[mid]==nums[mid+1]){
            if((mid)%2 == 0){                   //这里也是判断mid的前面数的总数是否是偶数，这里和上面判断的区别就是这里和mid相等的数再后面，不包含在mid的前面，所以如果前面的数都是成对的话，那肯定那个单独的数就在mid的后面。
                l=mid+2;
            }else{
                r=mid-1;
            }
        }else if(nums[mid]!=nums[mid-1]&&nums[mid]!=nums[mid+1]){
            return nums[mid];
        }
    }
    return -1;
}

另外，你会发现即使数组没有经过排序，只要将同一元素放在一起，该算法仍然起作用（例：[10, 10, 4, 4, 7, 11, 11, 12, 12, 2, 2]）。他们的顺序无关紧要，重要的是含有单个元素的子数组元素个数为奇数。

时间复杂度：O(logn)。在每次循环迭代中，我们将搜索空间减少了一半。
空间复杂度：O(1)，仅使用了常数空间。

附加解法：仅对偶数索引进行二分搜索

事实证明我们只需要对偶数索引进行二分搜索。这种方法与方法二都是不错的方法，但是该方法比方法二更加优雅。
在该算法中，我们对所有偶数索引进行搜索，直到遇到第一个其后元素不相同的索引。
我们可以使用二分搜索替代线性搜索。
在单个元素的后面，则成对的元素变为奇数索引后跟他们的同一元素。说明我们在检索单个元素后面的偶数索引时，其后都没有它的同一元素。因此，我们可以通过偶数索引确定单个元素在左侧还是右侧。

算法：

奇数长度的数组首尾元素索引都为偶数，因此我们可以将 lo 和 hi 设置为数组首尾。
我们需要确保 mid 是偶数，如果为奇数，则将其减 1。
然后，我们检查 mid 的元素是否与其后面的索引相同。
如果相同，则我们知道 mid 不是单个元素。且单个元素在 mid 之后。则我们将 lo 设置为 mid + 2。
如果不是，则我们知道单个元素位于 mid，或者在 mid 之前。我们将 hi 设置为 mid。
一旦 lo == hi，则当前搜索空间为 1 个元素，那么该元素为单个元素，我们将返回它。

var singleNonDuplicate = function(nums) {
    let lo = 0;
        let hi = nums.length - 1;
        while (lo < hi) {
            let mid = lo + (hi - lo) / 2;
            if (mid % 2 == 1) mid--;
            if (nums[mid] == nums[mid + 1]) {
                lo = mid + 2;
            } else {
                hi = mid;
            }
        }
        return nums[lo];
    }
}

278. 第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例:

给定 n = 5，并且 version = 4 是第一个错误的版本。

调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true

所以，4 是第一个错误的版本。

题解

首先，暴力解法就是依次遍历每一个数然后判断其是否为第一个版本错误的数，这样时间复杂度比较高，所以我第一个想到的就是二分查找，代码很好写，但是在运行过程中遇到了一个怎么也解决不了的问题，在代码进行了标注，请仔细查看。

/**
 * Definition for isBadVersion()
 * 
 * @param {integer} version number
 * @return {boolean} whether the version is bad
 * isBadVersion = function(version) {
 *     ...
 * };
 */

/**
 * @param {function} isBadVersion()
 * @return {function}
 */
var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */

    return function(n) {    
        let l = 1,r = n;
        while(l<r){
            let mid = Math.floor((l+r)/2);    //当时没有加Math.floor()，然后执行代码的时候老是出问题，记住每次都进行一个向下取整
            if(isBadVersion(mid) == false){
                l = mid+1;
            }else{
                r = mid;
            }
        }
        return r;     //这里返回l,r都可以，因为跳出条件的条件是l和r相等
    };

};

时间复杂度：O(logn)。搜索空间每次减少一半，因此时间复杂度为O(logn)。
空间复杂度：O(1)。

153. 寻找旋转排序数组中的最小值

假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。

请找出其中最小的元素。

示例 1：

输入：nums = [3,4,5,1,2]
输出：1

示例 2：

输入：nums = [4,5,6,7,0,1,2]
输出：0

示例 3：

输入：nums = [1]
输出：1

题解

1.暴力解法,就是纯遍历

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
  let l=0,r;
  for(r=1;r<=nums.length-1;r++){
      if(nums[l]<nums[r]){
          l++;
      }else if(nums[l]>=nums[r]){
          return nums[r]
      }
  }
return nums[0];
};

2.二分查找,

在这个改进版本的二分搜索算法中，我们需要找到这个点。下面是关于变化点的特点：

所有变化点左侧元素 > 数组第一个元素

所有变化点右侧元素 < 数组第一个元素

算法

找到数组的中间元素 mid。

如果中间元素 > 数组第一个元素，我们需要在 mid 右边搜索变化点。

如果中间元素 < 数组第一个元素，我们需要在 mid 左边搜索变化点。

var findMin = function(nums) {
     let l=0,r=nums.length-1;
    if(nums.length == 1 ||nums[r]>nums[l]){   //首先判断数组是否只有一个值或者是数组就没有旋转，还是一个升序数组，这样就返回数组中第一个数值。
        return nums[0]
    }
    while(l<=r){                             
        mid = Math.floor((l+r)/2);
        if(nums[mid]<nums[0]){
            r = mid-1;
        }else if(nums[mid]>=nums[0]){
            l = mid+1;
        }
        
    }
    return nums[l];
}

这是参考别人写的，比较的是中值和右边的值。详情见https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/solution/er-fen-cha-zhao-wei-shi-yao-zuo-you-bu-dui-cheng-z/

 var findMin = function(nums) {
    var left = 0;
    var right = nums.length - 1;
    while (left < right) {
        var mid = (left + right) >> 1;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
};

154. 寻找旋转排序数组中的最小值 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

请找出其中最小的元素。

注意数组中可能存在重复的元素。

示例 1：

输入: [1,3,5]
输出: 1

示例 2：

输入: [2,2,2,0,1]
输出: 0

题解

比较中间数和最右侧的数，若二者相等，则将尾部元素从范围内删除。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let l=0,r=nums.length-1;
    if(nums.length == 1 || nums[l]<nums[r]){
        return nums[0];
    }
    while(l<r){
        mid = Math.floor((l+r)/2);
        if(nums[mid] == nums[r]){         //其实比上面的一题中只多了一个等于的条件哦，如果等于，就把后面相等的值都删掉再进行比较。
            r--;
        }else if(nums[mid]<nums[r]){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    return nums[l];
 
};

34. 在排序数组中查找元素的第一个和最后一个位置

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

题解

解法一：

先用二分法找到该元素的中间位置
然后开始向两边扩展

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let l = 0,r = nums.length-1;
    while(l<=r){
        mid = Math.floor((l+r)/2);
        if(nums[mid]==target){
            let start = mid;
            let end = mid;
            while(end<=r&&nums[end] == nums[end+1]){end++;}
            while(start>=l&&nums[start] == nums[start-1]){start--;}
            return [start,end];
        }else if(nums[mid]<target){
            l = mid+1;
        }else{
            r = mid-1;
        }
    }
    return [-1,-1]
};

解法二：

使用js自带的api解决此题，复杂度较高。

var searchRange = function(nums, target) {
    let start = nums.indexOf(target);     //查找数组中第一个值为target的索引
    let end = nums.lastIndexOf(target);   //查找数组中最后一个值为target的索引
    return [start,end]
}

解法三：

var searchRange = function(nums, target) {
    let left = 0, right = nums.length - 1, mid;
    while (left <= right) {
        mid = (left + right) >> 1;
        if (nums[mid] === target) break;            //其实和第一种解法一样，只是这里用了break的方法，碰到与目标值相等的值后直接跳出循环，然后查找数组中与target值相等的有几个。
        if (nums[mid] > target) right = mid - 1;
        else left = mid + 1;
    }
    if(left > right) return [-1, -1];
    let i = mid, j = mid;
    while(nums[i] === nums[i - 1]) i--;
    while(nums[j] === nums[j + 1]) j++;
    return [i, j];

}