二分查找

704. 二分查找

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

示例 1:

  1. 输入: nums = [-1,0,3,5,9,12], target = 9
  2. 输出: 4
  3. 解释: 9 出现在 nums 中并且下标为 4

答案：

  1. // （版本一）左闭右闭区间
  3. var search = function(nums, target) {
  4.     let l = 0, r = nums.length - 1;
  5.     // 区间 [l, r]
  6.     while(l <= r) {
  7.         let mid = (l + r) >> 1;   //右移一位，相当于除以2取整
  8.         if(nums[mid] === target) return mid;
  9.         let isSmall = nums[mid] < target;
  10.         l = isSmall ? mid + 1 : l;
  11.         r = isSmall ? r : mid - 1;
  12.     }
  13.     return -1;
  14. };
  16. // （版本二）左闭右开区间
  18. var search = function(nums, target) {
  19.     let l = 0, r = nums.length;
  20.     // 区间 [l, r）
  21.     while(l < r) {
  22.         let mid = (l + r) >> 1;
  23.         if(nums[mid] === target) return mid;
  24.         let isSmall = nums[mid] < target;
  25.         l = isSmall ? mid + 1 : l;
  26.         // 所以 mid 不会被取到
  27.         r = isSmall ? r : mid;
  28.     }
  29.     return -1;
  30. };

278. 第一个错误的版本

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

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

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

答案：

  1. var solution = function(isBadVersion) {
  2.     /**
  3.      * @param {integer} n Total versions
  4.      * @return {integer} The first bad version
  5.      */
  6.     return function(n) {
  7.         let left = 1, right = n;
  8.         while (left < right) { // 循环直至区间左右端点相同
  9.             const mid = Math.floor(left + (right - left) / 2); // 防止计算时溢出
  10.             if (isBadVersion(mid)) {
  11.                 right = mid; // 答案在区间 [left, mid] 中
  12.             } else {
  13.                 left = mid + 1; // 答案在区间 [mid+1, right] 中
  14.             }
  15.         }
  16.         // 此时有 left == right，区间缩为一个点，即为答案
  17.         return left;
  18.     };
  19. };

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

  1. var searchInsert = function (nums, target) {
  2.   let l = 0, r = nums.length - 1, ans = nums.length;
  4.   while (l <= r) {
  5.     const mid = l + Math.floor((r - l) >> 1);
  7.     if (target > nums[mid]) {
  8.       l = mid + 1;
  9.     } else {
  10.       ans = mid;
  11.       r = mid - 1;
  12.     }
  13.   }
  15.   return ans;
  16. };

剑指 Offer II 006. 排序数组中两个数字之和

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

  1. var twoSum1 = function(numbers, target) {
  2.     //从数组第一个元素开始，用二分查找函数判断后面的元素是否为target-numbers[i]
  3.     for (let i = 0; i < numbers.length; i++) {
  4.         const x = numbers[i]
  5.         const index = binarySearch(numbers, i + 1, numbers.length - 1, target - x)
  6.         if (index != -1) {
  7.             return [i, index]
  8.         }
  9.     }
  10.     return []
  11. };
  12. //定义二分查找的函数
  13. var binarySearch = function(number, left, right, target) {
  14.     while (left <= right) {
  15.         const mid = left + Math.floor((right - left) / 2)
  16.         if (target == number[mid]) {
  17.             return mid;
  18.         } else if (target < number[mid]) {
  19.             right = mid - 1
  20.         } else {
  21.             left = mid + 1
  22.         }
  23.     }
  24.     return -1
  25. }

剑指 Offer II 069. 山峰数组的顶部

符合下列属性的数组 arr 称为 山峰数组（山脉数组） ：

arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i ，即山峰顶部。

  1. var peakIndexInMountainArray = function(arr) {
  2.     let l = 0,r = arr.length - 1,ans = Math.max(...arr)
  3.     while(l <= r) {
  4.         let mid = (l + r) >> 1;
  5.         if(arr[mid]==ans) return mid;
  6.         if(arr[mid] < arr[mid+1]) {
  7.             l = mid + 1
  8.         } else {
  9.             r = mid - 1
  10.         }
  11.     }
  12.     return -1
  13. }

剑指 Offer II 068. 查找插入位置

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

  1. var searchInsert = function(nums, target) {
  2.     let l = 0, r = nums.length - 1;
  3.     while(l<=r) {
  4.         var mid = (l+r) >> 1;
  5.         if(nums[mid] == target) return mid;
  6.         if(nums[mid] < target) {
  7.             l = mid+1;
  8.         } else {
  9.             r = mid - 1
  10.         }
  11.     }
  12.     return l;
  13. }

374. 猜数字大小

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

-1：我选出的数字比你猜的数字小 pick < num
1：我选出的数字比你猜的数字大 pick > num
0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
返回我选出的数字。

  1. var guessNumber = function(n) {
  2.     let l = 1, r = n;
  3.     while(l <= r) {
  4.         let mid = Math.floor((l + r)/2);
  5.         if(guess(mid) == 0) {
  6.             return mid;
  7.         } else if (guess(mid) == 1){
  8.             l = mid + 1;
  9.         } else {
  10.             r = mid - 1
  11.         }
  12.     }
  13. };

69. x 的平方根

给你一个非负整数 x ，计算并返回 x 的 平方根 。

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

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

  1. var mySqrt = function(x) {
  2.     let l = 1, r= x;
  3.     while(l<=r) {
  4.         let mid = Math.floor((l+r)/2);
  5.         if(mid*mid == x) return mid;
  6.         if(mid*mid > x) {
  7.             r = mid - 1
  8.         } else {
  9.             l = mid + 1
  10.         }
  11.     }
  12.     return l - 1
  13. };