JavaScript算法题总结（二）二分查找/排序

 /* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param target int整型 
 * @return int整型
 */
function search( nums ,  target ) {
    // write code here
    let len = nums.length;
    if(!len)return -1;
    let [left , right] = [0 , len -1];
    while(left <= right){
        let mid = left + Math.floor((right - left) /2);
        let num = nums[mid];
        if(num === target) return mid;
        else if(num > target) right = mid - 1;
        else left = mid +1;
        
    }
    return -1;
}
module.exports = {
    search : search
};

function Find(target, array)
{
  //判断数组是否为空
  let m = array.length;
  if(m == 0)  return false;
  
  let n = array[0].length;
  if(n == 0)  return false;
  
  let i=0, j=n-1;//右上角元素
  while(i<m && j>=0){
    if(target < array[i][j]){
      j--;
    }else if(target > array[i][j]){
      i++;
    }else{
      return true;
    }
  }
  return false;
}
module.exports = {
    Find : Find
};

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
 */
function findPeakElement( nums ) {
    // write code here
    let [left,right]=[0,nums.length-1];
    while(left<right){
        let mid = left + Math.floor((right - left) / 2)
        if(nums[mid]<nums[mid+1])
            left=mid+1;
        else
            right=mid;
    }
    return left
}
module.exports = {
    findPeakElement : findPeakElement
};

let countReverse = 0;
const kmod = 1000000007;
function InversePairs(data)
{    
    mergeSort(data);
    return countReverse;
}

//归并排序
function mergeSort(arr, len = arr.length){
    const mid = Math.floor(len/2);
    if(len <= 1){
        return arr;
    }
    const left = mergeSort(arr.slice(0 , mid))
    const right = mergeSort(arr.slice(mid , len))
    console.log("left , right",left , right)
    const res = mergeOrderly(left,right);
    console.log("res",res)
    return res;
}

//合并子序列，累加逆序对
function mergeOrderly(left,right){
    let i = 0, j = 0;
    let newList = [];
    if(!left || !right){
        return; 
    }
    while (i < left.length && j < right.length){
        if(left[i] > right [j]){
            countReverse += left.length - i;
            countReverse %= kmod;
            newList.push(right [j]);
            j++;
        }else{
            newList.push(left [i]);
            i++;  
        }
    }
    if(i < left.length){
        newList = newList.concat(left.slice(i,left.length))
    }else{
        newList = newList.concat(right.slice(j,right.length))
    }
    return newList;
}
module.exports = {
    InversePairs : InversePairs
};

function minNumberInRotateArray(rotateArray)
{
  let left = 0, right = rotateArray.length-1;
    
  while(left < right){
    let mid = Math.floor( (left + right)/2 );
    //旋转点在右侧
    if(rotateArray[mid] < rotateArray[right]){
      right = mid;
    }
    //旋转点在左侧
    else if(rotateArray[mid] > rotateArray[right]){
      left = mid+1;
    }
    //缩小判断范围
    else{
      right--;
    }
  }
  return rotateArray[left];
}
module.exports = {
    minNumberInRotateArray : minNumberInRotateArray
};

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 比较版本号
 * @param version1 string字符串 
 * @param version2 string字符串 
 * @return int整型
 */
function compare( version1 ,  version2 ) {
    // write code here
    let arr1=version1.split('.');
    let arr2=version2.split('.');
    let i=0;
    while(i<arr1.length||i<arr2.length){
         let x=0,y=0;
        if(i<arr1.length) x=parseInt(arr1[i]);
        if(i<arr2.length) y=parseInt(arr2[i]);
        if(x>y) return 1;
        if(x<y) return -1;
        i++;
    }
    return 0;
}
module.exports = {
    compare : compare
};