• 33. 搜索旋转排序数组
• 34. 在排序数组中查找元素的第一个和最后一个位置
• 35. 搜索插入位置
• 69. x 的平方根
• 74. 搜索二维矩阵
• 81. 搜索旋转排序数组 II
• 153. 寻找旋转排序数组中的最小值
• 162. 寻找峰值
• 167. 两数之和 II - 输入有序数组
• 268. 丢失的数字
• 278. 第一个错误的版本
• 287. 寻找重复数
• 367. 有效的完全平方数
• 374. 猜数字大小

总结

做了十几道二分查找的题，一开始做的时候，总是拿不定判断条件，容易陷入死循环。

做到后面发现其实就两种模式。

一种是要我们寻找一个切确的值，这个时候，我们是可以通过nums[mid] === target找到这个值并返回的，这时的循环条件为while(left <= right)，代码模板大概为

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let left = 0;
    let right = x;
    while(left <= right) {
        let mid = Math.round((left + right) / 2);
        if (x === result) {
            return mid
        } else if(x < result) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};

另一种是寻找的值是不确定的，例如是数组中的最小值，我们拿到nums[mid]时，并不能直接判断是不是最小值。这时的循环条件为while(left < right)，并且right = mid。代码模板大概为

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let left = 0;
    let right = x;
    while(left < right) {
        let mid = Math.floor((left + right) / 2);
        if(x < result) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return right;
};

如果不是很明白，建议刷刷下面这些题，刷完基本就明白了。

33. 搜索旋转排序数组

这道题的关键是先找出有序的，然后判断target是否是在这个有序的，不是的话则是在另一段

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let len = nums.length;
    let left = 0;
    let right = len - 1;
    while(left <= right) {
        let mid = Math.round((left + right) / 2);
        if(nums[mid] === target) return mid;
        if(nums[left] <= nums[mid]) {
            if(nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }else {
            if(nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            }else {
                right = mid -1;
            }
        }
    }
    return -1
};

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

这道题的关键在于，我们利用二分查找出target值后，怎么继续利用二分查找找到第一个target和最后一个target。

思路就分成两次寻找。

第一次，找第一个target：在找到target后，right = mid -1;

第二次，找最后一个target：在找到target后，left = mid + 1;

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let leftIndex = findLeftTarget(nums, target);
    let rightIndex = findRightTarget(nums, target);
    return [leftIndex, rightIndex]
};

function findLeftTarget(nums, target) {
    let len = nums.length;
    let left = 0; 
    let right = len - 1;
    let res = -1;
    while(left <= right) {
        let mid = Math.round((left + right) / 2);
        if(nums[mid] === target) {
            right = mid -1;
            res = mid; // 记录最新的target的位置
        } else if(nums[left] <= target && target < nums[mid]) {
            right = mid -1;
        } else if(nums[mid] < target && target <= nums[right]){
            left = mid + 1;
        } else {
            break; // 都不符合，退出循环
        }
    }
    return res;
}
function findRightTarget(nums, target) {
    let len = nums.length;
    let left = 0; 
    let right = len - 1;
    let res = -1;
    while(left <= right) {
        let mid = Math.round((left + right) / 2);
        if(nums[mid] === target) {
            left = mid + 1;
            res = mid; // 记录最新的target的位置
        } else if(nums[left] <= target && target < nums[mid]) {
            right = mid -1;
        } else if(nums[mid] < target && target <= nums[right]){
            left = mid + 1;
        } else {
            break; // 都不符合，退出循环
        }
    }
    return res;
}

封装一下代码

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let leftIndex = findTarget(nums, target, 'left');
    let rightIndex = findTarget(nums, target, 'right');
    return [leftIndex, rightIndex]
};

function findTarget(nums, target, bound) {
    let len = nums.length;
    let left = 0; 
    let right = len - 1;
    let res = -1;
    while(left <= right) {
        let mid = Math.round((left + right) / 2);
        if(nums[mid] === target) {
            if (bound === 'left') { // 找第一个的
                right = mid - 1;
            } else { // 找最后一个的
                left = mid + 1;
            } 
            res = mid; // 记录最新的target的位置
        } else if(nums[left] <= target && target < nums[mid]) {
            right = mid -1;
        } else if(nums[mid] < target && target <= nums[right]){
            left = mid + 1;
        } else {
            break; // 都不符合，退出循环
        }
    }
    return res;
}

35. 搜索插入位置

本题的关键在于找到target后，返回target索引，否则返回left。

比较简单，不写了。

69. x 的平方根

这道题的关键在于，

初始化left = 1;right = x;

如果mid * mid === x, 则mid为所求。

当退出循环后，没找到mid，只能说明不存在刚刚好mid * mid === x，所以要返回left - 1或者是right。 为什么？ 因为 值肯定就处于right 和left直接（退出循环的时候，left = right+1）;

而要取整，所以就只能取左边的，及right 或者 left -1;

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function(x) {
    let left = 0;
    let right = x;
    while(left <= right) {
        let mid = Math.round((left + right) / 2);
        let result = mid * mid;
        if (x === result) {
            return mid
        } else if(x < result) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left-1;
};

74. 搜索二维矩阵

这道题又两种二分查找的思路，

第一种是先利用二分查找在哪一行，然后再在这一行当中利用二分查找。

第二种是将多行数组拼接成一个数组，然后二分查找。

太简单了，不写。

81. 搜索旋转排序数组 II

这道题跟之前那道是类似的，只不过多了个重复元素，所以就多了些判断。 因为会出现这种情况。

例如 ：

nums=[3,1,2,3,3,3,3]。target=2，首次二分时无法判断区间[0,3] 和区间 [4,6] 哪个是有序的。

对于这种情况，我们只能将当前二分区间的左边界加一，右边界减一，然后在新区间上继续二分查找。

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let len = nums.length;
    let left = 0;
    let right = len - 1;
    while(left <= right) {
        let mid = Math.round((left + right) / 2);
        if(nums[mid] === target){
             return true;
        }else if(nums[left] === nums[mid] && nums[mid] === nums[right]) {
            left++;
            right--;
        }else if(nums[left] <= nums[mid]) {
            if(nums[left] <= target && target < nums[mid]) {
                right = mid - 1;
            }else {
                left = mid + 1;
            }
        }else {
            if(nums[mid] < target && target <= nums[right]) {
                left = mid + 1;
            }else {
                right = mid -1;
            }
        }
    }
    return false
};

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

在二分查找的每一步中，左边界为 low，右边界为high，区间的中点为 pivot，最小值就在该区间内。我们将中轴元素 。

nums[pivot]与右边界元素 nums[high]进行比较，可能会有以下的三种情况：

第一种情况是 nums[pivot]< nums[high]

如下图所示，这说明 nums[pivot] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。

第二种情况是 nums[pivot]>nums[high]。如下图所示，这说明 nums[pivot] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。

由于数组不包含重复元素，并且只要当前的区间长度不为 1。 pivot 就不会与high 重合；而如果当前的区间长度为 1，这说明我们已经可以结束二分查找了。因此不会存在 nums[pivot]=nums[high] 的情况。

当二分查找结束时，我们就得到了最小值所在的位置。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    while(left < right) {
        let mid = Math.floor((left + right) /2 );
        if(nums[mid] < nums[right]) {
            right = mid;
        }else {
            left = mid + 1;
        }
    }
    return nums[left];
};

这里为什么用left < right,Math.floor((left + right) /2 );，right = mid; 跟前面的题都不太一样。

这就是因为，这道题是找一个最小值，不是一个确却的值，我们没有条件可以直接用===来判断是查找到target元素，所以只能不断试探。

而nums[mid] < nums[right]，这个nums[mid]可能就是target，也可能不是，所以就只能写出right = mid;保留起来。

再继续看后面的题，你就会发现这个规律，只要不是确切的值，都是套用这个模板。

162. 寻找峰值

这道题跟上一道题一样，同样不是寻找确切的值，所以可以套用上面的模板。 当 nums[mid] > nums[mid+1]时，说明nums[mid]可能是峰值，或者峰值在左边。所以right = mid。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function(nums) {
    let left = 0;
    let right = nums.length - 1;
    while(left < right) {
        let mid = Math.floor((left + right) / 2);
        if(nums[mid] > nums[mid + 1]) {
            right = mid
        }else {
            left = mid + 1;
        }
    }
    return right
};

167. 两数之和 II - 输入有序数组

这道题，要用二分查找的话，思路是先用一层循环遍历数组，然后在每次遍历中用二分查找。

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(numbers, target) {
    let right = numbers.length - 1;
    for(let i = 0; i < numbers.length -1; i++) {
        let num = target - numbers[i];
        let left = i + 1;
        while(left <= right) {
            let mid = Math.round((left + right) / 2);
            if(num === numbers[mid]) {
                return [i+1, mid +1];
            }else if(numbers[left] <= num && num < numbers[mid]) {
                right = mid -1;
            }else if(numbers[mid] < num && num <= numbers[right]) {
                left = mid + 1;
            }else {
                break;
            }
        }
        
    }
    return [-1, -1]
};

268. 丢失的数字

先进行排序，然后再判断nums[i]是否 > i,是的话，i可能是target，也可能在左边，所以right = mid;

不过需要注意可能丢失的是最后一个数字n，所以需要再循环后面加个判断。

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function(nums) {
    nums = nums.sort();
    let left = 0;
    let right = nums.length - 1;
    while(left < right) {
        let mid = Math.floor((left + right) / 2);
        if(nums[mid] > mid) {
            right = mid
        }else {
            left = mid + 1;
        }
    }
    if(left === nums.length -1 && nums[left] === left) return nums.length;
    return left;
};

278. 第一个错误的版本

这道题跟上道类似，解法一毛一样。

var solution = function(isBadVersion) {
    /**
     * @param {integer} n Total versions
     * @return {integer} The first bad version
     */
    return function(n) {
        let left = 1;
        let right = n;
        while(left < right) {
            let mid = Math.floor((left + right) / 2);
            if(isBadVersion(mid)) {
                right = mid
            }else {
                left = mid + 1;
            }
        }
        return left;
    };
};

287. 寻找重复数

这道题的关键在于 利用抽屉原理， 把所有小于mid的数加起来，如果count>mid,说明 重复数在 1...mid 中。否则在 mid+1 ... n中。

/**
 * @param {number[]} nums
 * @return {number}
 */
var findDuplicate = function(nums) {
    let left = 1;
    let right = nums.length - 1;
    while(left < right) {
        let mid = Math.floor((left + right) / 2);
        let count = 0;
        for(let i of nums) {
            if(i <= mid) {
                count++;
            }
        }
        if(count > mid) {
            right = mid;
        }else {
            left = mid + 1;
        }
    } 
    return left;
};

367. 有效的完全平方数

这道题比较简单，比上面又一道类似的更加简单。

/**
 * @param {number} num
 * @return {boolean}
 */
var isPerfectSquare = function(num) {
    let left = 1;
    let right = num;
    while(left <= right) {
        let mid = Math.floor((left + right) / 2);
        if(mid * mid === num) {
            return true;
        }else if(mid * mid > num) {
            right = mid - 1;
        }else {
            left = mid + 1;
        }
    }
    return false;
};

374. 猜数字大小

挺简单的，就是纯粹写个二分查找的算法。不写了

欢迎去我的github查看更多文章 github:github.com/Sunny-lucki…