https://labuladong.github.io/algo/2/19/52/
https://labuladong.github.io/algo/1/9/
https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md

基础理论

https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md
适用场景：

数组有序
无重复元素（如果有重复元素），元素下标可能不是唯一

框架：

//arr为排序数组
============== 递归实现 ==================
function Binary_search(arr,beigin,end,target){
    if(beigin>end) {
        return false
    }
    var mid = Math.floor((left+right)/2)
    if(arr[mid] == target){
        return true
    }
    if(arr[mid]<target){
        return Binary_search(arr,begin,mid-1,target)
    }
    if(arr[mid]>target){
        return Binary_search(arr,begin+1,end,target)
    }
}
============== 循环实现 ==================
function Binary_search(arr,target){
    var begin =0;
    var end=arr.length-1;
    while(begin<end){
     var mid = Math.floor((left+right)/2)
        if(target == arr[mid]){
            return true
        }
        if(target > arr[mid]){
            begin = mid+1
        }
        if(target >arr[mid]){
            end = mid-1
        }
    }
}

// （版本一）左闭右闭区间
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
/**
var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    // 使用左闭右闭区间
    while (left <= right) {
        let mid = left + Math.floor((right - left)/2);
        if (nums[mid] > target) {
            right = mid - 1;  // 去左面闭区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右面闭区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};
// （版本二）左闭右开区间
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let left = 0, right = nums.length;
    // 使用左闭右开区间 [left, right)
    while (left < right) {
        let mid = left + Math.floor((right - left)/2);
        if (nums[mid] > target) {
            right = mid;  // 去左区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};

练习

704. 二分查找

var search = function(nums, target) {
    let left = 0, right = nums.length - 1;
    // 使用左闭右闭区间
    while (left <= right) {
        let mid = left + Math.floor((right - left)/2);
        if (nums[mid] > target) {
            right = mid - 1;  // 去左面闭区间寻找
        } else if (nums[mid] < target) {
            left = mid + 1;   // 去右面闭区间寻找
        } else {
            return mid;
        }
    }
    return -1;
};

34. 在排序数组中查找元素的第一个和最后一个位置

两个二分法分别找左边界和右边界


var searchRange = function(nums, target) {
    var left = leftBound(nums,target);
    var right = rightBound(nums,target);
    return [left,right]
};
//[...1,3,3,3,3,5,6..]
//     mid
//查找左端点
function leftBound(nums,target){
    var left=0;
    var right=nums.length-1;
    while(left <= right){
        var mid=  Math.floor((right+left)/2);
        if(nums[mid] == target) {
            if(mid == 0 || nums[mid-1]<target){
                return mid  //该位置是左端点
            }
            right = mid-1
        }else if(nums[mid]<target){
            left = mid+1;
        }else if(nums[mid]>target){
            right = mid-1;
        }
    }
    return -1;
}
//[...1,3,3,3,3,5,6..]
//           mid
//查找右端点
function rightBound(nums,target){
    var left=0;
    var right=nums.length-1;
    while(left <= right){
        var mid = Math.floor((right+left)/2);
        if(nums[mid] ==target) {
            if(mid == nums.length-1 || nums[mid+1]>target){
                return mid  //该位置是右端点
            }
            left = mid+1
        }else if(nums[mid]<target){
            left = mid+1;
        }else if(nums[mid]>target){
            right = mid-1;
        }
    }
    return -1;    
}

35. 搜索插入位置

var searchInsert = function(nums, target) {

    var left =0;
    var right = nums.length-1;
    var index = -1;
    //index是最终元素的下标，如果没有找到就是元素的插入位置
    while(left <= right){
        var mid =left +  Math.floor((right-left)/2)
        if(nums[mid]==target){
             index = mid
        } else if (nums[mid]>target){
            if(mid ==0 || nums[mid-1]<target){
                index = mid
            }
            right = mid-1; 
        }else if(target > nums[mid]){
            if(mid == nums.length-1 || target<nums[mid+1]){
                index = mid+1
            }
            left = mid+1
        }       
    }   
     return index;  
};

4. 寻找两个正序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。
https://www.bilibili.com/video/av55640101?from=search&seid=16181943450989372605
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例 2:
nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

分析：

思路：
时间复杂度提示使用二分法，合并数组中找到合适分界点，是中位数。
合并数组过程中，蓝色区域始终小于黄色区域，需要满足L1<=R2,L2<=R1
从较短数组开始二分

有序数组中位数
function getMidian(num){
var len = num.length
return (num[Math.floor((len-1)/2)]+num[Math.floor(len/2)]) /2
}

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    //从较短数组开始遍历
    if(nums1.length > nums2.length) [nums1,nums2]=[nums2,nums1]

    var len1 = nums1.length;
    var len2 = nums2.length;

    //如果数组1为空 直接返回数组2的中位数
    if(len1 === 0){
        return (nums2[Math.floor((len2-1)/2)]+ nums2[Math.floor(len2/2)])/2
    }

    var len = len1+len2;
    var start1 = 0
    var end1 = len1; //?
    var cut1,cut2; //数组num1 num2分割线左边元素个数

    while(start1<=end1){
        cut1 = Math.floor((start1+end1)/2);
        //len+1  最后个数为奇数的时候，返回为左侧的最大值
        cut2 = Math.floor((len+1)/2)-cut1;  

        var L1 = cut1 === 0?-Infinity:nums1[cut1-1];
        var L2 = cut2 === 0?-Infinity:nums2[cut2-1];
        var R1 = cut1 === len1?Infinity:nums1[cut1];
        var R2 = cut2 === len2?Infinity:nums2[cut2];

        if(L1 > R2){
            end1 = cut1-1 
        } else if (L2 > R1){
            start1 = cut1+1   
        } else {
            if(len%2 === 0){
                return (Math.max(L1,L2) + Math.min(R1,R2))/2
            } else {
                return Math.max(L1,L2)
            }
        }
    }
    return -1 
};