230403-分治

重要的两点

• 如何找出基线条件
• 如何缩小计算规模

示例

/**
 * 计算元素的和
 */
function sum(arr: number[]) {
  if (arr.length === 0) {
    return 0;
  }
  if (arr.length === 1) {
    return arr[0];
  }
  let [c, ...rest] = arr;
  return c + sum(rest);
}

let a =  sum([2, 4, 6]);
console.log(a);

/**
 * 计算元素的长度
 */
function ArrayLength(arr: number[]) {
  if (arr.length === 0) {
    return 0;
  }
  let [i, ...rest] = arr;
  return 1 + ArrayLength(rest);
}

let a = ArrayLength([2, 4, 6]);
console.log(a);

/**
 * 找出元素中的最大值
 */
function maxNumber(arr: number[]) {
  if (arr.length === 0) {
    return -Infinity;
  }
  let [i, ...rest] = arr;
  let max = maxNumber(rest);
  return i > max ? i : max;
}

let a = maxNumber([-1]);
console.log(a);


/**
 * 二分查找，分治方法
 */
function midSearch(arr: number[], search: number) {
  if (arr.length === 0) {
    return -1;
  }
  if (arr[0] === search) {
    return arr[0];
  }
  let mid = (arr.length - 1) / 2;
  if (arr[mid] > search) {
    return midSearch(arr.slice(0, mid), search);
  } else {
    return midSearch(arr.slice(mid, arr.length), search);
  }
}

// 分治，二分查找，Rust版本
fn mid_search(arr: Vec<i32>, search: i32) -> i32 {
    if arr.len() == 0 {
        return -1;
    }
    if arr[0] == search {
        return arr[0];
    }
    let mid = (arr.len() - 1) / 2;
    if arr[mid] > search {
        return mid_search(arr[0..mid].to_vec(), search);
    } else {
        return mid_search(arr[mid..arr.len()].to_vec(), search);
    }
}