二分查找
关键词： 排序数组
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）。
数组既可能是整体排序的，也可能是分段排序的，但一旦题目是对于排序数组并且还有查找操作，那么二分查找算法总是值得尝试的。
在排序数组中二分查找
- 查找插入地位
输出一个排序的整数数组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);};