乐趣区

关于二分查找:算法二分查找

jiezi

二分查找

关键词：排序数组

var binarySearch = (nums, target) => {
  let left = 0;
  let right = nums.length -1

  while(left <= right) {const mid = left + Math.floor((right - left)/2)
    
    if(nums[mid] == traget) {return mid}

    if (nums[mid] > target) {right = mid - 1} else {left = mid + 1}
  }
  return -1
}

二分查找算法每次将查找范畴缩小一半，因而对于一个长度为 n 的数组可能须要 O（logn） 次查找，每次查找只须要比拟以后查找范畴的两头数字和指标数字，在 O（1） 的工夫能够实现，因而二分查找算法的工夫复杂度是O（logn）。

数组既可能是整体排序的，也可能是分段排序的，但一旦题目是对于排序数组并且还有查找操作，那么二分查找算法总是值得尝试的。

在排序数组中二分查找

  1. 查找插入地位

输出一个排序的整数数组 nums 和一个目标值 t，如果数组 nums 中蕴含 t，则返回 t 在数组中的下标；如果数组 nums 中不蕴含 t，则返回将 t 按程序插入数组 nums 中的下标。假如数组中没有雷同的数字。例如，输出数组 nums 为[1，3，6，8]，如果目标值 t 为 3，则输入 1；如果 t 为 5，则返回 2。

var searchInsert = function(nums, target) {
  let left = 0
  let right = nums.length - 1
  while(left <= right) {let mid = left + Math.floor((right - left) / 2)

    if(nums[mid] >= target) {if(mid == 0 || nums[mid - 1] < target) {return mid}
      right = mid  - 1
    } else {left = mid + 1}
  }
  return nums.length
}
  1. 山峰数组的顶部

在一个长度大于或等于 3 的数组中，任意相邻的两个数字都不相等。该数组的前若干数字是递增的，之后的数字是递加的，因而它的值看起来像一座山峰。请找出山峰顶部，即数组中最大值的地位。例如，在数组 [1，3，5，4，2] 中，最大值是 5，输入它在数组中的下标 2。

不难想到直观的解法来解决这个题目，即逐个扫描整个数组，通过比拟就能找出数组中的最大值。显然，这种解法的工夫复杂度是 O（n）。


/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function (arr) {
    let left = 0
    let right = arr.length - 1
    let mid
    while (left <= right) {mid = left + Math.floor((right - left) / 2)

        if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {return mid} else if (arr[mid] > arr[mid + 1]) {right = mid;} else {left = mid + 1;}
    };
    return mid
}
  1. 排序数组中只呈现一次的数字

在一个排序的数组中，除一个数字只呈现一次之外，其余数字都呈现了两次，请找出这个惟一只呈现一次的数字。例如，在数组 [1，1，2，2，3，4，4，5，5] 中，数字 3 只呈现了一次。

/**
 * @param {number[]} nums
 * @return {number}
 */
var singleNonDuplicate = function(nums) {
    let low = 0, high = nums.length - 1;
    while (low < high) {const mid = Math.floor((high - low) / 2) + low;
        if (nums[mid] === nums[mid ^ 1]) {low = mid + 1;} else {high = mid;}
    }
    return nums[low];
};
  1. 按权重生成随机数

输出一个正整数数组 w，数组中的每个数字 w[i]示意下标 i 的权重，请实现一个函数 pickIndex 依据权重比例随机抉择一个下标。例如，如果权重数组 w 为[1，2，3，4]，那么函数 pickIndex 将有 10% 的概率抉择 0、20% 的概率抉择 1、30% 的概率抉择 2、40% 的概率抉择 3。

能够创立另一个和权重数组的长度一样的数组 sums，新数组的第 i 个数值 sums[i]是权重数组中前 i 个数字之和。有了这个数组 sums 就能很不便地依据等概率随机生成的数字 p 依照权重比例抉择下标。

var Solution = function(w) {pre = new Array(w.length).fill(0);
    pre[0] = w[0];
    for (let i = 1; i < w.length; ++i) {pre[i] = pre[i - 1] + w[i];
    }
    this.total = _.sum(w);
};

Solution.prototype.pickIndex = function() {
    // 生成随机数
    const x = Math.floor((Math.random() * this.total)) + 1;
    const binarySearch = (x) => {
        let low = 0, high = pre.length - 1;
        while (low < high) {const mid = Math.floor((high - low) / 2) + low;
            // 一直迫近
            if (pre[mid] < x) {low = mid + 1;} else {high = mid;}
        }
        return low;
    }
    return binarySearch(x);
};

在数值范畴内二分查找(TODO)

退出移动版