总结

1、一涉及到有序数组，就要想到用二分查找解决。关于二分查找主题：https://leetcode-cn.com/leetbook/read/binary-search/

1 一个有序数组

1.1 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。链接：https://leetcode-cn.com/problems/binary-search

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

输入: nums = [-1,0,3,5,9,12], target = 9

输出: 4

解释: 9 出现在 nums 中并且下标为 4

1.1.1 返回任意一个

public class HalfQuery {
    public static int query(int value,List<Integer> input,int beg,int end){
        // 中止条件为大于等于
        if(beg>=end){
            if(input.get(beg) == value){
                return beg;
            }else {
                return -1;
            }
        }

        int mid = (beg+end)/2;
        if(input.get(mid) > value){
            return query(value,input,beg,mid-1);
        }else if(input.get(mid) < value) {
            return query(value,input,mid+1,end);
        }else {
            return mid;
        }
    }

    public static void main(String[] args){
        List<Integer> input = Lists.newArrayList(2,5);
        System.out.printf(query(0,input,0,input.size()-1)+"");
    }
}

public class HalfQuery {

public static int query(int value,List<Integer> input,int beg,int end){

// 中止条件为大于等于

if(beg>=end){

if(input.get(beg) == value){

return beg;

}else {

return -1;

}

int mid = (beg+end)/2;

if(input.get(mid) > value){

return query(value,input,beg,mid-1);

}else if(input.get(mid) < value) {

return query(value,input,mid+1,end);

}else {

return mid;

}

public static void main(String[] args){

List<Integer> input = Lists.newArrayList(2,5);

System.out.printf(query(0,input,0,input.size()-1)+"");

}

1.1.2 返回index最小

有时候有相同数，我们需要返回index最下的数，此时就是

  public int findBinary(int x, int[] arr, int beg, int end) {
        if (beg >= end) {
            return beg;
        }

        int mid = (beg + end) / 2;

        // 2.与二分查找稍微不同,这里有个等号,为了在相等时,获取最小的元素。
        if (arr[mid] >= x) {
            return findBinary(x, arr, beg, mid);
        } else {
            return findBinary(x, arr, mid + 1, end);
        }

    }

public int findBinary(int x, int[] arr, int beg, int end) {

if (beg >= end) {

return beg;

}

int mid = (beg + end) / 2;

// 2.与二分查找稍微不同,这里有个等号,为了在相等时,获取最小的元素。

if (arr[mid] >= x) {

return findBinary(x, arr, beg, mid);

} else {

return findBinary(x, arr, mid + 1, end);

}

1.2 找到 K 个最接近的元素

给定一个排序好的数组，两个整数 k 和 x，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。如果有两个数与 x 的差值一样，优先选择数值较小的那个数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-k-closest-elements

输入: [1,2,3,4,5], k=4, x=-1
输出: [1,2,3,4]

1 2	输入: [1,2,3,4,5], k=4, x=-1 输出: [1,2,3,4]

算法：

二分查找时，两个数与 x 的差值一样，优先选择数值较小的那个数。

二分找到position时，需要确定真正最小的位置

  if (position > 0 && Math.abs(arr[position - 1] - x) <= d) {
      minPostion--;
  }
   if (position < (arr.length - 2)
                && Math.abs(arr[position + 1] - x) < d) {
      minPostion++;
  }

if (position > 0 && Math.abs(arr[position - 1] - x) <= d) {

minPostion--;

}

if (position < (arr.length - 2)

&& Math.abs(arr[position + 1] - x) < d) {

minPostion++;

}

计算差要取绝对值

public class FindKNearest {

    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int position = findBinary(x, arr, 0, arr.length - 1);


        int minPostion = position;
        int d = Math.abs(arr[position] - x);

        // 确定真正的最下值
        if (position > 0 && Math.abs(arr[position - 1] - x) <= d) {
            minPostion--;
        }
        if (position < (arr.length - 2)
                && Math.abs(arr[position + 1] - x) < d) {
            minPostion++;
        }

        List<Integer> result = new ArrayList<Integer>();
        List<Integer> lresult = new ArrayList<Integer>();
        List<Integer> rresult = new ArrayList<Integer>();

        // 注意减法操作,因为一定包含arr[minpositon]
        k--;

        int left = minPostion - 1;
        int right = minPostion + 1;
        while (k > 0) {
            int ld = Integer.MAX_VALUE;
            int rd = Integer.MAX_VALUE;
            if (left >= 0) {
                ld = Math.abs(arr[left] - x);
            }
            if (right < arr.length) {
                rd = Math.abs(arr[right] - x);
            }
            if (ld <= rd) {
                lresult.add(arr[left]);
                left--;
            } else {
                rresult.add(arr[right]);
                right++;
            }
            k--;
        }

        // 翻转操作
        for (int i = lresult.size() - 1; i >= 0; i--) {
            result.add(lresult.get(i));
        }
        result.add(arr[minPostion]);
        result.addAll(rresult);
        return result;

    }

    public int findBinary(int x, int[] arr, int beg, int end) {
        if (beg >= end) {
            return beg;
        }

        int mid = (beg + end) / 2;

        // 与二分查找稍微不同,这里有个等号,为了在相等时,获取最小的元素。
        if (arr[mid] >= x) {
            return findBinary(x, arr, beg, mid);
        } else {
            return findBinary(x, arr, mid + 1, end);
        }

    }

    public static void main(String[] args) {
        FindKNearest findKNearest = new FindKNearest();
        int[] input = new int[]{1, 3};
        List<Integer> ouput = findKNearest.findClosestElements(input, 1, 2);
        System.out.println(ouput);
    }
}

public class FindKNearest {

public List<Integer> findClosestElements(int[] arr, int k, int x) {

int position = findBinary(x, arr, 0, arr.length - 1);

int minPostion = position;

int d = Math.abs(arr[position] - x);

// 确定真正的最下值

if (position > 0 && Math.abs(arr[position - 1] - x) <= d) {

minPostion--;

}

if (position < (arr.length - 2)

&& Math.abs(arr[position + 1] - x) < d) {

minPostion++;

}

List<Integer> result = new ArrayList<Integer>();

List<Integer> lresult = new ArrayList<Integer>();

List<Integer> rresult = new ArrayList<Integer>();

// 注意减法操作,因为一定包含arr[minpositon]

k--;

int left = minPostion - 1;

int right = minPostion + 1;

while (k > 0) {

int ld = Integer.MAX_VALUE;

int rd = Integer.MAX_VALUE;

if (left >= 0) {

ld = Math.abs(arr[left] - x);

}

if (right < arr.length) {

rd = Math.abs(arr[right] - x);

}

if (ld <= rd) {

lresult.add(arr[left]);

left--;

} else {

rresult.add(arr[right]);

right++;

}

k--;

}

// 翻转操作

for (int i = lresult.size() - 1; i >= 0; i--) {

result.add(lresult.get(i));

}

result.add(arr[minPostion]);

result.addAll(rresult);

return result;

}

public int findBinary(int x, int[] arr, int beg, int end) {

if (beg >= end) {

return beg;

}

int mid = (beg + end) / 2;

// 与二分查找稍微不同,这里有个等号,为了在相等时,获取最小的元素。

if (arr[mid] >= x) {

return findBinary(x, arr, beg, mid);

} else {

return findBinary(x, arr, mid + 1, end);

}

public static void main(String[] args) {

FindKNearest findKNearest = new FindKNearest();

int[] input = new int[]{1, 3};

List<Integer> ouput = findKNearest.findClosestElements(input, 1, 2);

System.out.println(ouput);

}

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

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array

实例1
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

实例2
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

实例1

输入: nums = [5,7,7,8,8,10], target = 8

输出: [3,4]

实例2

输入: nums = [5,7,7,8,8,10], target = 6

输出: [-1,-1]

方案1 先快排找到位置，再顺序找

算法：

二分查找，实现查找一个元素，返回index最下的元素坐标
需要在外层判断if(nums[position] != target)

class Solution {
    public int[] searchRange(int[] nums, int target) {
             if(nums.length == 0){
                   return new int[]{-1,-1};
             }
            int position = findBinary(target,nums,0,nums.length-1);

            // 1.因为在二分查找中没有使用相等判断，所以这里需要判断
            if(nums[position] != target){
                return new int[]{-1,-1};
            }
            int[] result = new int[]{position,position};
            int end = position;
            while(position<nums.length){
                if(nums[position] == target){
                    end = position;
                        position++;
                }else{
                    break;
                }
            
            }
            result[1] = end;
            return result;
            
    }


     public int findBinary(int x, int[] arr, int beg, int end) {
        if (beg >= end) {
            return beg;
        }

        int mid = (beg + end) / 2;

        // 2.与二分查找稍微不同,这里有个等号,为了在相等时,获取最小的元素。
        if (arr[mid] >= x) {
            return findBinary(x, arr, beg, mid);
        } else {
            return findBinary(x, arr, mid + 1, end);
        }

    }
}

class Solution {

public int[] searchRange(int[] nums, int target) {

if(nums.length == 0){

return new int[]{-1,-1};

}

int position = findBinary(target,nums,0,nums.length-1);

// 1.因为在二分查找中没有使用相等判断，所以这里需要判断

if(nums[position] != target){

return new int[]{-1,-1};

}

int[] result = new int[]{position,position};

int end = position;

while(position<nums.length){

if(nums[position] == target){

end = position;

position++;

}else{

break;

}

result[1] = end;

return result;

}

public int findBinary(int x, int[] arr, int beg, int end) {

if (beg >= end) {

return beg;

}

int mid = (beg + end) / 2;

// 2.与二分查找稍微不同,这里有个等号,为了在相等时,获取最小的元素。

if (arr[mid] >= x) {

return findBinary(x, arr, beg, mid);

} else {

return findBinary(x, arr, mid + 1, end);

}

方案2 通过两次快排完成

class Solution {
    public int[] searchRange(int[] nums, int target) {
             if(nums.length == 0){
                   return new int[]{-1,-1};
             }
            int position = findBinary(target,nums,0,nums.length-1,true);

            // 1.因为在二分查找中没有使用相等判断，所以这里需要判断
            if(nums[position] != target){
                return new int[]{-1,-1};
            }
            int[] result = new int[]{position,position};
            int position2 = findBinary(target,nums,0,nums.length-1,false);
            if(nums[position2] == target){
                result[1]=position2;
            }
            return result;
            
    }

   public int findBinary(int x, int[] arr, int beg, int end, boolean isMin) {
        if (beg >= end) {
            return beg;
        }

        int mid = (beg + end) / 2;
        // 2.与二分查找稍微不同,这里有个等号,为了在相等时,获取最小的元素。
        if (arr[mid] >= x) {
             // 需要获取最大的那个index时候，还需要如下条件，注意要加上arr[mid] == arr[mid + 1]
            if (arr[mid] == x && !isMin && arr[mid] == arr[mid + 1]) {
                return findBinary(x, arr, mid + 1, end, isMin);
            } else {
                return findBinary(x, arr, beg, mid, isMin);
            }
        } else {
            return findBinary(x, arr, mid + 1, end, isMin);
        }
    }
}

class Solution {

public int[] searchRange(int[] nums, int target) {

if(nums.length == 0){

return new int[]{-1,-1};

}

int position = findBinary(target,nums,0,nums.length-1,true);

// 1.因为在二分查找中没有使用相等判断，所以这里需要判断

if(nums[position] != target){

return new int[]{-1,-1};

}

int[] result = new int[]{position,position};

int position2 = findBinary(target,nums,0,nums.length-1,false);

if(nums[position2] == target){

result[1]=position2;

}

return result;

}

public int findBinary(int x, int[] arr, int beg, int end, boolean isMin) {

if (beg >= end) {

return beg;

}

int mid = (beg + end) / 2;

// 2.与二分查找稍微不同,这里有个等号,为了在相等时,获取最小的元素。

if (arr[mid] >= x) {

// 需要获取最大的那个index时候，还需要如下条件，注意要加上arr[mid] == arr[mid + 1]

if (arr[mid] == x && !isMin && arr[mid] == arr[mid + 1]) {

return findBinary(x, arr, mid + 1, end, isMin);

} else {

return findBinary(x, arr, beg, mid, isMin);

}

} else {

return findBinary(x, arr, mid + 1, end, isMin);

}

2 自旋数组

山脉数组是一条折线。自旋数组是平行线。

2.1 寻找自选数据的最小值

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof

 1、没有旋转情况  1,3,3  -》1
 2、考虑重复的数  3,3,3,1 -》 1
 3、无重复，输入：[3,4,5,1,2] 输出：1

1、没有旋转情况 1,3,3 -》1

2、考虑重复的数 3,3,3,1 -》 1

3、无重复，输入：[3,4,5,1,2] 输出：1

算法： 核心就是确定递归的beg和end。

class Solution {
    public int minArray(int[] numbers) {
           int min = findMin(numbers,0,numbers.length-1);

           return Math.min(min,numbers[0]);
    }

    int findMin(int[] numbers,int beg,int end){
        if (beg >= end) {
            return numbers[beg];
        }
        int mid = (beg + end) / 2;

        // 关键确定在左旋转边
        if (numbers[mid] < numbers[end]) {
            end = mid;
        } else if (numbers[mid] > numbers[end]) {
            beg = mid + 1;
        } else {
            end--;
        }
       return findMin(numbers,beg,end);
    }


}

class Solution {

public int minArray(int[] numbers) {

int min = findMin(numbers,0,numbers.length-1);

return Math.min(min,numbers[0]);

}

int findMin(int[] numbers,int beg,int end){

if (beg >= end) {

return numbers[beg];

}

int mid = (beg + end) / 2;

// 关键确定在左旋转边

if (numbers[mid] < numbers[end]) {

end = mid;

} else if (numbers[mid] > numbers[end]) {

beg = mid + 1;

} else {

end--;

}

return findMin(numbers,beg,end);

}

3两个有序数组

3.1 查找第K个数

输入两个有序数组，查找第K个元素，比如：

输入：[1,2]，[1,3]，第2个

输出：2

算法如下：

每次查询k/2个数。存在数组长度小于k/2的情况，所以需要每个数组的对应的k/2位置为：Math.min(len1, k / 2)。

三个截止条件。

    // 1.三个结束条件
        int len1 = end1 - beg1 + 1;
        int len2 = end2 - beg2 + 1;
        if (len1 <= 0) {
            return input2.get(beg2 + k - 1);
        }
        if (len2 <= 0) {
            return input1.get(beg1 + k - 1);
        }
        if (k == 1) {
            return Math.min(input1.get(beg1), input2.get(beg2));
        }

// 1.三个结束条件

int len1 = end1 - beg1 + 1;

int len2 = end2 - beg2 + 1;

if (len1 <= 0) {

return input2.get(beg2 + k - 1);

}

if (len2 <= 0) {

return input1.get(beg1 + k - 1);

}

if (k == 1) {

return Math.min(input1.get(beg1), input2.get(beg2));

}

代码

/**
 * 查找第K个数
 */
public class FindK {
    public int findK(List<Integer> input1, List<Integer> input2, int k) {
        return find(input1, 0, input1.size() - 1,
                input2, 0, input2.size() - 1, k);
    }

    private int find(List<Integer> input1, int beg1, int end1,
                     List<Integer> input2, int beg2, int end2,
                     int k) {

         // 1.三个结束条件
        int len1 = end1 - beg1 + 1;
        int len2 = end2 - beg2 + 1;
        if (len1 <= 0) {
            return input2.get(beg2 + k - 1);
        }
        if (len2 <= 0) {
            return input1.get(beg1 + k - 1);
        }
        if (k == 1) {
            return Math.min(input1.get(beg1), input2.get(beg2));
        }

        // 2. 递归
        int mid1 = Math.min(len1, k / 2);
        int mid2 = Math.min(len2, k / 2);
        if (input1.get(beg1 + mid1 - 1) >= input2.get(beg2 + mid2 - 1)) {
            return find(input1, beg1, end1, input2, beg2 + mid2, end2, k - mid2);
        } else {
            return find(input1, beg1 + mid1, end1, input2, beg2, end2, k - mid1);
        }
    }

    public double findMid(List<Integer> input1, List<Integer> input2) {
        int mid = 0;
        int length1 = input1.size();
        int length2 = input2.size();
        if ((length1 + length2) % 2 == 0) {
            mid = (length1 + length2 - 2) / 2;
            double n1 = findK(input1, input2, mid);
            double n2 = findK(input1, input2, mid + 1);
            return (n1 + n2) / 2;
        } else {
            mid = (length1 + length2 - 1) / 2;
            return findK(input1, input2, mid);
        }

    }

    public static void main(String[] args) {
        List<Integer> input1 = Arrays.asList(1, 3);
        List<Integer> input2 = Arrays.asList(2);
        FindK find = new FindK();

       System.out.println(find.findK(input1, input2, 2));
    }
}

/**

* 查找第K个数

public class FindK {

public int findK(List<Integer> input1, List<Integer> input2, int k) {

return find(input1, 0, input1.size() - 1,

input2, 0, input2.size() - 1, k);

}

private int find(List<Integer> input1, int beg1, int end1,

List<Integer> input2, int beg2, int end2,

int k) {

// 1.三个结束条件

int len1 = end1 - beg1 + 1;

int len2 = end2 - beg2 + 1;

if (len1 <= 0) {

return input2.get(beg2 + k - 1);

}

if (len2 <= 0) {

return input1.get(beg1 + k - 1);

}

if (k == 1) {

return Math.min(input1.get(beg1), input2.get(beg2));

}

// 2. 递归

int mid1 = Math.min(len1, k / 2);

int mid2 = Math.min(len2, k / 2);

if (input1.get(beg1 + mid1 - 1) >= input2.get(beg2 + mid2 - 1)) {

return find(input1, beg1, end1, input2, beg2 + mid2, end2, k - mid2);

} else {

return find(input1, beg1 + mid1, end1, input2, beg2, end2, k - mid1);

}

public double findMid(List<Integer> input1, List<Integer> input2) {

int mid = 0;

int length1 = input1.size();

int length2 = input2.size();

if ((length1 + length2) % 2 == 0) {

mid = (length1 + length2 - 2) / 2;

double n1 = findK(input1, input2, mid);

double n2 = findK(input1, input2, mid + 1);

return (n1 + n2) / 2;

} else {

mid = (length1 + length2 - 1) / 2;

return findK(input1, input2, mid);

}

public static void main(String[] args) {

List<Integer> input1 = Arrays.asList(1, 3);

List<Integer> input2 = Arrays.asList(2);

FindK find = new FindK();

System.out.println(find.findK(input1, input2, 2));

}

3.2 中位数

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

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

方法1 通过合并有序数组实现O(M+N)

1、思路

合并有序数组

2、算法

public class FindMidNum {

    public double findMedianSortedArrays(List<Integer> input1, List<Integer> input2) {
        List<Integer> result = new ArrayList<Integer>();

        merge(input1, 0, input2, 0, result);

        // 偶数
        double output = 0;
        if (result.size() % 2 == 0) {
            int mid = (result.size() - 2) / 2;
            double left = result.get(mid);
            double right = result.get(mid + 1);
            output = (left + right) / 2;
        } else {
            int mid = (result.size() -1) / 2;
            output = result.get(mid);

        }
        return output;
    }
    
    // 三个查询条件
    public void merge(List<Integer> input1, int beg1, List<Integer> input2, int beg2,
                      List<Integer> mResult) {
        if (beg1 >= input1.size() && beg2 >= input2.size()) {
            return;
        }

        if (beg1 < input1.size() && beg2 < input2.size()) {
            if (input1.get(beg1) < input2.get(beg2)) {
                mResult.add(input1.get(beg1));
                merge(input1, beg1 + 1, input2, beg2, mResult);
            } else {
                mResult.add(input2.get(beg2));
                merge(input1, beg1, input2, beg2 + 1, mResult);
            }
        } else if (beg1 < input1.size()) {
            mResult.add(input1.get(beg1));
            merge(input1, beg1 + 1, input2, beg2, mResult);
        } else if (beg2 < input2.size()) {
            mResult.add(input2.get(beg2));
            merge(input1, beg1, input2, beg2 + 1, mResult);
        }
    }

    public static void main(String[] args) {
        List<Integer> input1 = Arrays.asList(1, 2);
        List<Integer> input2 = Arrays.asList(3, 4);
        FindMidNum fid = new FindMidNum();

        System.out.println(fid.findMedianSortedArrays(input1, input2));
    }

}

public class FindMidNum {

public double findMedianSortedArrays(List<Integer> input1, List<Integer> input2) {

List<Integer> result = new ArrayList<Integer>();

merge(input1, 0, input2, 0, result);

// 偶数

double output = 0;

if (result.size() % 2 == 0) {

int mid = (result.size() - 2) / 2;

double left = result.get(mid);

double right = result.get(mid + 1);

output = (left + right) / 2;

} else {

int mid = (result.size() -1) / 2;

output = result.get(mid);

}

return output;

}

// 三个查询条件

public void merge(List<Integer> input1, int beg1, List<Integer> input2, int beg2,

List<Integer> mResult) {

if (beg1 >= input1.size() && beg2 >= input2.size()) {

return;

}

if (beg1 < input1.size() && beg2 < input2.size()) {

if (input1.get(beg1) < input2.get(beg2)) {

mResult.add(input1.get(beg1));

merge(input1, beg1 + 1, input2, beg2, mResult);

} else {

mResult.add(input2.get(beg2));

merge(input1, beg1, input2, beg2 + 1, mResult);

}

} else if (beg1 < input1.size()) {

mResult.add(input1.get(beg1));

merge(input1, beg1 + 1, input2, beg2, mResult);

} else if (beg2 < input2.size()) {

mResult.add(input2.get(beg2));

merge(input1, beg1, input2, beg2 + 1, mResult);

}

public static void main(String[] args) {

List<Integer> input1 = Arrays.asList(1, 2);

List<Integer> input2 = Arrays.asList(3, 4);

FindMidNum fid = new FindMidNum();

System.out.println(fid.findMedianSortedArrays(input1, input2));

}

方法2 通过查找两个有序数组第K个数（O(Log(N+M))）

中位数分为两种情况

如果是奇数，有序数组的(length1 + length2 – 1) / 2为中位数，相当于查找数组中第(length1 + length2 – 1) / 2 + 1 的数。
如果是偶数，查找有序数组中(length1 + length2 – 2) / 2，(length1 + length2 ) / 2的数，相当于(length1 + length2 – 2) / 2 + 1 ，(length1 + length2 ) / 2 +1

public class FindMidNumLogN {
    /**
     * 计算中位数
     * @return
     */
    public double findMid(List<Integer> input1, List<Integer> input2) {
        int mid = 0;
        int length1 = input1.size();
        int length2 = input2.size();
        if ((length1 + length2) % 2 == 0) {
            mid = (length1 + length2 - 2) / 2;
          <span style="color: #ff0000;">  // 第k个元素,所以应该是计算坐标再+1</span>
            mid = mid + 1;
            double n1 = findK(input1, input2, mid);
            double n2 = findK(input1, input2, mid + 1);
            return (n1 + n2) / 2;
        } else {
            mid = (length1 + length2 - 1) / 2;
           <span style="color: #ff0000;"> // 第k个元素,所以应该是计算坐标再+1</span>
            mid = mid +1;
            return findK(input1, input2, mid );
        }

    }


    /**
     * 查找第k个数
     * @return
     */
    public int findK(List<Integer> input1, List<Integer> input2, int k) {
        return find(input1, 0, input1.size() - 1,
                input2, 0, input2.size() - 1, k);
    }

    private int find(List<Integer> input1, int beg1, int end1,
                     List<Integer> input2, int beg2, int end2,
                     int k) {

        int len1 = end1 - beg1 + 1;
        int len2 = end2 - beg2 + 1;
        if (len1 <= 0) {
            return input2.get(beg2 + k - 1);
        }
        if (len2 <= 0) {
            return input1.get(beg1 + k - 1);
        }
        if (k == 1) {
            return Math.min(input1.get(beg1), input2.get(beg2));
        }

        int mid1 = Math.min(len1, k / 2);
        int mid2 = Math.min(len2, k / 2);
        if (input1.get(beg1 + mid1 - 1) >= input2.get(beg2 + mid2 - 1)) {
            return find(input1, beg1, end1, input2, beg2 + mid2, end2, k - mid2);
        } else {
            return find(input1, beg1 + mid1, end1, input2, beg2, end2, k - mid1);
        }
    }

   

    public static void main(String[] args) {
        List<Integer> input1 = Arrays.asList(1, 3);
        List<Integer> input2 = Arrays.asList(2);
        FindMidNumLogN find = new FindMidNumLogN();

        System.out.println(find.findMid(input1, input2));
    }
}

public class FindMidNumLogN {

/**

* 计算中位数

* @return

public double findMid(List<Integer> input1, List<Integer> input2) {

int mid = 0;

int length1 = input1.size();

int length2 = input2.size();

if ((length1 + length2) % 2 == 0) {

mid = (length1 + length2 - 2) / 2;

<span style="color: #ff0000;"> // 第k个元素,所以应该是计算坐标再+1</span>

mid = mid + 1;

double n1 = findK(input1, input2, mid);

double n2 = findK(input1, input2, mid + 1);

return (n1 + n2) / 2;

} else {

mid = (length1 + length2 - 1) / 2;

<span style="color: #ff0000;"> // 第k个元素,所以应该是计算坐标再+1</span>

mid = mid +1;

return findK(input1, input2, mid );

}

/**

* 查找第k个数

* @return

public int findK(List<Integer> input1, List<Integer> input2, int k) {

return find(input1, 0, input1.size() - 1,

input2, 0, input2.size() - 1, k);

}

private int find(List<Integer> input1, int beg1, int end1,

List<Integer> input2, int beg2, int end2,

int k) {

int len1 = end1 - beg1 + 1;

int len2 = end2 - beg2 + 1;

if (len1 <= 0) {

return input2.get(beg2 + k - 1);

}

if (len2 <= 0) {

return input1.get(beg1 + k - 1);

}

if (k == 1) {

return Math.min(input1.get(beg1), input2.get(beg2));

}

int mid1 = Math.min(len1, k / 2);

int mid2 = Math.min(len2, k / 2);

if (input1.get(beg1 + mid1 - 1) >= input2.get(beg2 + mid2 - 1)) {

return find(input1, beg1, end1, input2, beg2 + mid2, end2, k - mid2);

} else {

return find(input1, beg1 + mid1, end1, input2, beg2, end2, k - mid1);

}

public static void main(String[] args) {

List<Integer> input1 = Arrays.asList(1, 3);

List<Integer> input2 = Arrays.asList(2);

FindMidNumLogN find = new FindMidNumLogN();

System.out.println(find.findMid(input1, input2));

}

4 山脉数组（先升再降、先降再升）

4.1 查看最小值(同5.1.2 查询峰谷)

问题：一个先降序再升序的数组，寻找最小值。

输入：[8，4，2，3，7]

输出：2

算法：参考下节中查看数组的峰谷

public class FindH {
 
    public int queryMin(List<Integer> input, int beg, int end) {
        // 两个中止
        if (beg >= end) {
            return beg;
        }

        int mid = (beg + end) / 2;
        // 说明最小数一定是在左边
        if (input.get(mid) < input.get(mid + 1)) {
            return queryMin(input, beg, mid);
        } else {
            return queryMin(input, mid+1, end);
        }
    }


    public static void main(String[] args) {
        // 先降后升
        List<Integer> input = Arrays.asList(8, 4, 2, 3, 7);

        // 单边降序,结果为1
        // List<Integer> input = Arrays.asList(7,5,1);

        // 单边增,结果为1,
        //List<Integer> input = Arrays.asList(1, 4, 9);

        FindH findH = new FindH();
        int position = findH.queryMid(input, 0, input.size() - 1);
        System.out.println(input.get(position));

    }
    
}

public class FindH {

public int queryMin(List<Integer> input, int beg, int end) {

// 两个中止

if (beg >= end) {

return beg;

}

int mid = (beg + end) / 2;

// 说明最小数一定是在左边

if (input.get(mid) < input.get(mid + 1)) {

return queryMin(input, beg, mid);

} else {

return queryMin(input, mid+1, end);

}

public static void main(String[] args) {

// 先降后升

List<Integer> input = Arrays.asList(8, 4, 2, 3, 7);

// 单边降序,结果为1

// List<Integer> input = Arrays.asList(7,5,1);

// 单边增,结果为1,

//List<Integer> input = Arrays.asList(1, 4, 9);

FindH findH = new FindH();

int position = findH.queryMid(input, 0, input.size() - 1);

System.out.println(input.get(position));

}

4.2 查找某一个值

问题：一个先降序再升序的数组，寻找k值。

输入：[8，4，2，3，7]，查询7

输出：4

算法实现思路：

STEP1 首先定位拐点。参考上面查找4.1中查找足queyMin方法。
STEP2 分别对两个数组进行二分查找，看在那个数组中。

public class FindH {
    public int findK(List<Integer> input, int key) {
        FindH findH = new FindH();
        int position = findH.queryMid(input, 0, input.size() - 1);
        System.out.println(input.get(position));


        int left1 = findH.queryBinary(input, key, 0, position, true);
        if (left1 != -1) {
            return left1;
        }
        int right1 = findH.queryBinary(input, key, position, input.size() - 1, false);
        return right1;

    }

    public int queryBinary(List<Integer> input, int key, int beg, int end, boolean isDes) {
        // 中止条件1
        if (beg >= end) {
            if (input.get(beg) == key) {
                return beg;
            } else {
                return -1;
            }
        }

        // 中止条件2
        int mid = (beg + end) / 2;
        if (input.get(mid) == key) {
            return mid;
        }

        // 中止条件3
        if (input.get(mid) > key) {
            if (isDes) {
                return queryBinary(input, key, mid + 1, end, isDes);
            } else {
                return queryBinary(input, key, beg, mid - 1, isDes);
            }
        } else {
            if (isDes) {
                return queryBinary(input, key, beg, mid - 1, isDes);
            } else {
                return queryBinary(input, key, mid + 1, end, isDes);
            }
        }
    }



    private int queryMin(List<Integer> input, int beg, int end) {
        // 两个中止
        if (beg >= end) {
            return beg;
        }

        int mid = (beg + end) / 2;
        if (input.get(mid) < input.get(mid + 1)) {
            return queryMin(input, beg, mid);
        } else {
            return queryMin(input, mid+1, end);
        }
    }


    public static void main(String[] args) {
        // 先降后升
        List<Integer> input = Arrays.asList(8, 4, 2, 3, 7);

        // 单边降序,结果为1
        // List<Integer> input = Arrays.asList(7,5,1);

        // 单边增,结果为1,
        //List<Integer> input = Arrays.asList(1, 4, 9);

        FindH findH = new FindH();
        int position = findH.queryMid(input, 0, input.size() - 1);
        System.out.println(input.get(position));

      System.out.println(findH.findK(input, 7));
    }
}

public class FindH {

public int findK(List<Integer> input, int key) {

FindH findH = new FindH();

int position = findH.queryMid(input, 0, input.size() - 1);

System.out.println(input.get(position));

int left1 = findH.queryBinary(input, key, 0, position, true);

if (left1 != -1) {

return left1;

}

int right1 = findH.queryBinary(input, key, position, input.size() - 1, false);

return right1;

}

public int queryBinary(List<Integer> input, int key, int beg, int end, boolean isDes) {

// 中止条件1

if (beg >= end) {

if (input.get(beg) == key) {

return beg;

} else {

return -1;

}

// 中止条件2

int mid = (beg + end) / 2;

if (input.get(mid) == key) {

return mid;

}

// 中止条件3

if (input.get(mid) > key) {

if (isDes) {

return queryBinary(input, key, mid + 1, end, isDes);

} else {

return queryBinary(input, key, beg, mid - 1, isDes);

}

} else {

if (isDes) {

return queryBinary(input, key, beg, mid - 1, isDes);

} else {

return queryBinary(input, key, mid + 1, end, isDes);

}

private int queryMin(List<Integer> input, int beg, int end) {

// 两个中止

if (beg >= end) {

return beg;

}

int mid = (beg + end) / 2;

if (input.get(mid) < input.get(mid + 1)) {

return queryMin(input, beg, mid);

} else {

return queryMin(input, mid+1, end);

}

public static void main(String[] args) {

// 先降后升

List<Integer> input = Arrays.asList(8, 4, 2, 3, 7);

// 单边降序,结果为1

// List<Integer> input = Arrays.asList(7,5,1);

// 单边增,结果为1,

//List<Integer> input = Arrays.asList(1, 4, 9);

FindH findH = new FindH();

int position = findH.queryMid(input, 0, input.size() - 1);

System.out.println(input.get(position));

System.out.println(findH.findK(input, 7));

}

5 无序数组

5.1 查找峰值/峰谷（二分）

5.1.1 查找峰值

峰值元素是指其值大于左右相邻值的元素。注意：峰值不是最大值。

给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。

数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-peak-element

输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5 
解释: 你的函数可以返回索引 1，其峰值元素为 2；
     或者返回索引 5， 其峰值元素为 6。

输入: nums = [1,2,1,3,5,6,4]

输出: 1 或 5

解释: 你的函数可以返回索引 1，其峰值元素为 2；

或者返回索引 5，其峰值元素为 6。

算法思想：mid和右边比较,如果mid大,则向左找最大,可以认为mid右边比它小。

算法实现：

为什么 mid和右边比较呢?mid = (beg + end) / 2;因为存在2个以及以上元素时,肯定存在mid+1,但是不一定存mid-1。
在(nums[mid] > nums[mid + 1])情况下，search(nums, beg, mid )不是search(nums, beg, mid -1)

**
 * 思想:
 * 
 */
public class FindPeek {

    public int findPeakElement(int[] nums) {
        return search(nums, 0, nums.length - 1);

    }

    private int search(int[] nums, int beg, int end) {
        if (beg >= end) {
            return beg;
        }
        int mid = (beg + end) / 2;
        // 1、因为存在2个以及以上元素时,肯定存在mid+1,不一定存mid-1。
        if (nums[mid] > nums[mid + 1]) {
            // 2.是mid,不是mid-1
            return search(nums, beg, mid );
        } else {
            return search(nums, mid+1 , end);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 1};
        FindPeek findPeek = new FindPeek();
        System.out.println(findPeek.findPeakElement(nums));
    }
}

* 思想:

public class FindPeek {

public int findPeakElement(int[] nums) {

return search(nums, 0, nums.length - 1);

}

private int search(int[] nums, int beg, int end) {

if (beg >= end) {

return beg;

}

int mid = (beg + end) / 2;

// 1、因为存在2个以及以上元素时,肯定存在mid+1,不一定存mid-1。

if (nums[mid] > nums[mid + 1]) {

// 2.是mid,不是mid-1

return search(nums, beg, mid );

} else {

return search(nums, mid+1 , end);

}

public static void main(String[] args) {

int[] nums = new int[]{1, 2, 3, 1};

FindPeek findPeek = new FindPeek();

System.out.println(findPeek.findPeakElement(nums));

}

5.1.2 查找峰谷

算法，通过峰谷

public class FindPeekValey {

    public int findPeakValeyElement(int[] nums) {
        return search(nums, 0, nums.length - 1);

    }

    private int search(int[] nums, int beg, int end) {
        if (beg >= end) {
            return beg;
        }
        int mid = (beg + end) / 2;
        // 1、因为存在2个以及以上元素时,肯定存在mid+1,不一定存mid-1。
        if (nums[mid] > nums[mid + 1]) {
            return search(nums,mid+1, end );
        } else {
            //2.是mid,不是mid-1
            return search(nums, beg , mid);
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 1};
        FindPeekValey findPeek = new FindPeekValey();
        System.out.println(findPeek.findPeakValeyElement(nums));
    }
}

public class FindPeekValey {

public int findPeakValeyElement(int[] nums) {

return search(nums, 0, nums.length - 1);

}

private int search(int[] nums, int beg, int end) {

if (beg >= end) {

return beg;

}

int mid = (beg + end) / 2;

// 1、因为存在2个以及以上元素时,肯定存在mid+1,不一定存mid-1。

if (nums[mid] > nums[mid + 1]) {

return search(nums,mid+1, end );

} else {

//2.是mid,不是mid-1

return search(nums, beg , mid);

}

public static void main(String[] args) {

int[] nums = new int[]{1, 2, 3, 1};

FindPeekValey findPeek = new FindPeekValey();

System.out.println(findPeek.findPeakValeyElement(nums));

}

Heart.Think.Do

常用算法-二分查找

总结

1 一个有序数组

1.1 二分查找

1.1.1 返回任意一个

1.1.2 返回index最小

1.2 找到 K 个最接近的元素

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

方案1 先快排找到位置，再顺序找

方案2 通过两次快排完成

2 自旋数组

2.1 寻找自选数据的最小值

3两个有序数组

3.1 查找第K个数

3.2 中位数

方法1 通过合并有序数组实现O(M+N)

方法2 通过查找两个有序数组第K个数（O(Log(N+M))）

4 山脉数组（先升再降、先降再升）

4.1 查看最小值(同5.1.2 查询峰谷)

4.2 查找某一个值

5 无序数组

5.1 查找峰值/峰谷（二分）

5.1.1 查找峰值

5.1.2 查找峰谷

Related Posts:

分类&标签

常用算法-二分查找

总结

1 一个有序数组

1.1 二分查找

1.1.1 返回任意一个

1.1.2 返回index最小

1.2 找到 K 个最接近的元素

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

方案1 先快排找到位置，再顺序找

方案2 通过两次快排完成

2 自旋数组

2.1 寻找自选数据的最小值

3两个有序数组

3.1 查找第K个数

3.2 中位数

方法1 通过合并有序数组实现O(M+N)

方法2 通过查找两个有序数组第K个数（O(Log(N+M))）

4 山脉数组（先升再降、先降再升）

4.1 查看最小值(同5.1.2 查询峰谷)

4.2 查找某一个值

5 无序数组

5.1 查找峰值/峰谷 （二分）

5.1.1 查找峰值

5.1.2 查找峰谷

Related Posts:

分类&标签

5.1 查找峰值/峰谷（二分）