leetcode刷题（javaScript）——分治思想（二分查找、快速排序）相关场景题总结

在实现这些分治算法时，通常会遵循以下逻辑：

1. 分解（Divide）：将原始问题分解成更小的子问题。这通常涉及将问题划分成相同规模的子问题，或者将问题划分成规模逐渐减小的子问题。

2. 解决（Conquer）：递归地解决子问题。对每个子问题递归地应用相同的算法，直到子问题规模足够小，可以直接求解。

3. 合并（Combine）：将子问题的解合并成原始问题的解。这一步通常涉及将子问题的解合并起来，得到原始问题的解。

快速排序

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  let mid = Math.floor(arr.length / 2);
  let pivot = arr.splice(mid, 1)[0];
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat(pivot).concat(quickSort(right));
}

二分查找

具体的二分查找算法如下：

1. 首先，确定数组的左边界和右边界，通常初始时左边界为0，右边界为数组长度减1。
2. 计算中间位置的索引，即(left + right) / 2。
3. 比较中间位置的元素与目标元素的大小关系：
   • 如果中间位置的元素等于目标元素，则找到了目标元素，返回其索引。
   • 如果中间位置的元素大于目标元素，则目标元素可能在左半部分，更新右边界为中间位置减1。
   • 如果中间位置的元素小于目标元素，则目标元素可能在右半部分，更新左边界为中间位置加1。
4. 重复步骤2和步骤3，直到找到目标元素或者左边界大于右边界。

二分查找的时间复杂度为O(log n)，其中n为数组的长度。由于每次查找都将数组规模减半，因此它的查找效率非常高。

 二分查找并插入元素示例：

function binarySearchInsert(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            // 如果找到目标元素，则直接插入在该位置
            arr.splice(mid, 0, target);
            return arr;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // 如果未找到目标元素，则插入在合适位置
    arr.splice(left, 0, target);
    return arr;
}

// 示例
const sortedArr = [1, 3, 5, 7, 9];
const target = 6;
const result = binarySearchInsert(sortedArr, target);
console.log(result);

704. 二分查找 

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

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

复杂度分析

    时间复杂度：O(log⁡n)O(\log n)O(logn)，其中 nnn 是数组的长度。

    空间复杂度：O(1)O(1)O(1)。

 

374. 猜数字大小

猜数字游戏的规则如下：

• 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
• 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。

你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

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

返回我选出的数字。

/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * var guess = function(num) {}
 */

/**
 * @param {number} n
 * @return {number}
 */
var guessNumber = function (n) {
    if (n == 1) return n;
    let left = 1, right = n;
    while (left <= right) {
        let mid = Math.floor((left + right) / 2);
        let gue = guess(mid);
        if (gue === 0) { return mid; }
        if (gue === -1) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
};

35. 搜索插入位置

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

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

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

69. x 的平方根 

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

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

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

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

367. 有效的完全平方数

给你一个正整数 num 。如果 num 是一个完全平方数，则返回 true ，否则返回 false 。

完全平方数 是一个可以写成某个整数的平方的整数。换句话说，它可以写成某个整数和自身的乘积。

不能使用任何内置的库函数，如  sqrt 。

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