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

分治思想是一种将问题分解成更小的子问题，然后解决子问题并将结果合并的算法设计策略。二分查找、快速排序和折半查找都属于分治思想的经典算法。在leetcode里，分治思想一般结合其他场景出现，构成复合型题目。但是在看题时一定要了解能否用分治思想去解决题目，避免使用复杂度过高的暴力解决方式；尤其是看到强调时间复杂度为O(logn)实现，那很可能是二分法了。

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

分解（Divide）：将原始问题分解成更小的子问题。这通常涉及将问题划分成相同规模的子问题，或者将问题划分成规模逐渐减小的子问题。
解决（Conquer）：递归地解决子问题。对每个子问题递归地应用相同的算法，直到子问题规模足够小，可以直接求解。
合并（Combine）：将子问题的解合并成原始问题的解。这一步通常涉及将子问题的解合并起来，得到原始问题的解。

快速排序

快速排序是一种经典的排序算法，采用了分治思想。其思想可以简单概括为以下几步：

选择一个基准元素（pivot）：从待排序数组中选择一个元素作为基准元素。

分区（Partition）：将数组中小于基准元素的元素放在基准元素的左边，大于基准元素的元素放在基准元素的右边，基准元素则位于最终排序位置。

递归排序：对基准元素左右两侧的子数组分别递归地应用快速排序算法。

合并：将左侧递归+基准元素+右侧递归合并返回。

快速排序的关键在于分区过程，通过不断地选择基准元素并分区，将数组分成两部分，左边部分小于基准元素，右边部分大于基准元素。递归地对左右两部分进行排序，最终实现整个数组的排序。快速排序的时间复杂度为O(nlogn)，在平均情况下具有较高的效率。

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));
}

二分查找

二分查找，也称为折半查找，是一种在有序数组中查找特定元素的算法。它的基本思想是将数组分成两部分，然后确定目标元素可能存在的那一部分，并继续在该部分进行查找，直到找到目标元素或者确定目标元素不存在。

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

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

最原始的二分查找题目，如果target存在，那么在left和right无限逼近时一定会遍历完所有的元素，肯定会找到mid下标。如果不存在，while循环结束直接返回-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

返回我选出的数字。

使用二分思想，找mid元素，通过leetcode提供的隐式guess方法获取mid是否找对。在left和right移动中，mid一定会找到该元素，因为一直都没找到，最后mid、left会和right重合，那么最后那个元素肯定是的了。

根据guess提供的-1还是1可以区分下次二分的位置是在左边还是右边

/** 
 * 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 。

这道题也是二分法的变种，只不过对中间元素的要求多了一步，即mid*mid要与x进行比较。

整体是对0-x进行折半查找，找到一个元素，使得它的平方接近于x。就要对left和right进行左右逼近目标元素。这里如果mid*mid=x则返回mid。如果没有，那么循环结束后左右指针会指向同一个元素，而这个元素的平方肯定大于x。题目要求向下取整，所以在循环外返回的是left-1

/**
 * @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 。

这道题跟上面是类似的，只不过不返回具体的值，而是true或false

/**
 * @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;
};