# 二分法

# 思想

针对有序数组进行查找时，优先考虑二分法。

# 题目

# 输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素 (opens new window)

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

# 思路

原数组为旋转数组，所以分界点前后都是有序的
进行二分查找，注意因为找最小值，high 赋值时应该从 mid 开始取，mid 可能是最小值
(right + left) / 2 === left + (right - left) / 2，左边的项需要考虑溢出问题，右边则利用减法规避

# 答案

function minArray(numbers: number[]): number {
  const n = numbers.length;
  let left = 0;
  let right = n - 1;

  while (left < right) {
    const mid = Math.floor(left + (right - left) / 2);
    if (numbers[mid] > numbers[right]) {
      left = mid + 1;
    } else if (numbers[mid] < numbers[right]) {
      right = mid;
    } else {
      right--;
    }
  }

  return numbers[left];
}

# 统计一个数字在排序数组中出现的次数 (opens new window)

统计一个数字在排序数组中出现的次数。

# 思路

先找出目标数字在数组中的位置
因为是排序数组，所以从目标位置开始从两边遍历，只要一不相等就可以退出循环

# 答案

function search(nums: number[], target: number): number {
  let count = 0;
  const n = nums.length;
  let left = 0;
  let right = n - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) {
      left = mid;
      break;
    } else if (nums[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  if (nums[left] !== target) return 0;

  let cl = left - 1;
  let cr = left + 1;
  count++;
  while (true) {
    if (nums[cl--] === target) count++;
    else break;
  }

  while (true) {
    if (nums[cr++] === target) count++;
    else break;
  }

  return count;
}

# 0~n-1中缺失的数字 (opens new window)

一个长度为 n-1 的递增排序数组中所有数字都是唯一的，并且每个数字都在范围 0 ～ n-1 之内。在范围 0～n-1 内的 n 个数字中有且只有一个数字不在该数组，请找出这个数字。

# 思路

left 指向0，right 指向最后一个元素
计算中间坐标 mid：
- 如果 mid = nums[mid]，说明 [0, mid] 范围内不缺失数字，left 更新为 mid + 1
- 如果 mid < nums[mid]，说明 [mid, right] 范围内不缺失数字，right 更新为 mid - 1
检查 left 是否小于等于 mid，若成立，返回第二步，否则继续往下执行
返回 left

# 答案

function missingNumber(nums: number[]) {
  let left = 0, right = nums.length - 1
  while(left <= right) {
    const mid = Math.floor((left + right) / 2)
    if(mid === nums[mid]) {
      left = mid + 1
    } else {
      right = mid -1
    }
  }
  return left
}

# 最长上升子序列 (opens new window)

给定一个无序的整数数组，找到其中最长上升子序列的长度。

示例：

输入：[10, 9, 2, 5, 3, 7, 101, 18]

输出：4

解释：最长上升的子序列是 [2, 3, 7, 101]，它的长度是 4

# 思路

维护一个子序列存放当前的上升序列
将当前数与子序列最大值比较，如果比最大值大直接加入队尾，如果更新则找一个合适的位置替换当前的元素

# 答案

function lengthOfLIS(nums: number[]): number {
  const n = nums.length
  if(n <= 1) return n
  
  const tail = [nums[0]]
  for(let i = 0; i < n; i++) {
    if(nums[i] > tail[tail.length - 1]) {
      tail.push(nums[i]) // 思路 1
    } else {
      let left = 0
      let right = tail.length - 1
      while(left < right) {
        let mid = Math.floor((left + right) / 2)
        if(tail[mid] < nums[i]) {
          left = mid + 1
        } else {
          right = mid
        }
      }
      tail[left] = nums[i]
    }
  }
  return tail.length
}

# 搜索二维矩阵II (opens new window)

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

每行的元素从左到右升序排列

每列的元素从上到下升序排列

# 思路

输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

选取左下角的值作为初始值 key
如果目标值大于 key，因为是最左边的值（最小），所以 col++
如果目标值小于 key，那么更小的值只能是上一行，所以 row--

# 答案

function searchMatrix(matrix: number[][], target: number): boolean {
  const rows = matrix.length
  if(rows <= 0) return false
  const cols = matrix[0].length
  if(cols <= 0) return false
  
  let row = rows - 1
  let col = 0
  while(row >= 0 && col < cols) {
    if(matrix[row][col] > target) {
      row--
    } else if(matrix[row][col] < target) {
      col++
    } else return true
  }
  return false
}

# Pow(x, n) (opens new window)

实现 pow(x, n) ，即计算 x 的 n 次幂函数

function myPow(x: number, n: number): number {
  if(!x) return 0
  if(n < 0) return 1 / myPow(x, -n)
  if(n % 2) return x * myPow(x, n - 1)
  return myPow(x * x, n / 2)
}

# 求交集 (opens new window)

function intersection(nums1: number[], nums2: number[]): number[] {
  let res = new Set<number>();
  nums2.sort((a, b) => a - b);

  function binarySearch(arr: number[], val: number): boolean {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
      let mid = Math.floor((left + right) / 2);
      if (arr[mid] === val) return true;
      else if (arr[mid] > val) right = mid - 1;
      else left = mid + 1;
    }
    return false;
  }

  for (let i = 0; i < nums1.length; i++) {
    if (binarySearch(nums2, nums1[i])) {
      res.add(nums1[i]);
    }
  }

  return [...res];
}

← README.md 二叉树.md →