【算法】二分查找【算法】二分查找

二分查找关键词：排序数组

var binarySearch = (nums, target) => { let left = 0; let right = nums.length -1while(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）。

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

在排序数组中二分查找

查找插入位置

输入一个排序的整数数组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 }

山峰数组的顶部

在一个长度大于或等于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，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]; };

按权重生成随机数

输入一个正整数数组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)