前端算法Hot 100 _二分查找

二分查找

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @param target int整型* @return int整型*/
function search(nums, target) {// write code hereif (nums.length === 0) return -1;let left = 0;let right = nums.length - 1;//取等于与不取等于（建议取，考虑长度为1）while (left <=right) {let mid = Math.floor((left + right) / 2);let val = nums[mid];if (val === target) return mid;else if (val < target) {left = mid + 1;} else {right = mid-1;}}return -1;
}
module.exports = {search: search,
};

找峰值（⭐）

step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。
step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。
step 3：如果中间值小于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。
step 4：最后区间收尾相遇的点一定就是波峰。

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/
function findPeakElement( nums ) {// write code here//很巧妙想法！！！//找中间点，判断其右侧的值是否递增，递增就向右边找峰值，否则向左侧找let right=nums.length-1;let left=0;while(left<right){let mid=Math.floor((left+right)/2);if(nums[mid]<nums[mid+1]){left=mid+1;}else{right=mid;}}return left;}
module.exports = {findPeakElement : findPeakElement
};

数组中的逆序对（⭐）

分治

• 与归并排序不同，此处要记录count值，要注意自行定义一个mergeSort，且合的过程借助两个指针记录并累加count
• 核心：count+=leftPart.length-i; //!!!key!!!和过程中了，left已经排序完了，左侧当前及其后面的数都会比右侧当前数大！！！count–，err，没有考虑左侧数组当前后续的值也比此右侧当前值大

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param nums int整型一维数组* @return int整型*/
function InversePairs(nums) {// write code here//读懂题目，是任意两个前后数字，没有要求是挨着的//基础：取模% 取余///看到nlogn->归并排序（堆几率不大对于前端）//作用域，count是全局状态！！！let count = 0;//分const mergeSort = (nums) => {//分if (nums.length <= 1) return nums;let mid = Math.floor