在一个排好序的数组中插入一个数，要求插入后依然保持顺序

思路

通过折半查找插入的位置，插入的位置应该具备nums[mid]>=target && nums[mid-1]<=target，也就是说插入值介于中间值和中间值前一位之间，然后就可以直接将这个值插入到中间值的位置，然后将中间值及其之后的元素向后移动一位

流程图

image.png

代码实现

package 笔试题;

import java.util.ArrayList;
import java.util.List;

public class DichotomyFind {

    public static void main(String[] args) {

        List<Integer> nums = new ArrayList<>();
        for (int i = 0; i < 15; i++) {
            nums.add(i*2);
        }
        method(nums, 14);
        for (Integer num : nums) {
            System.out.print(num + " ");
        }
    }

    /**
     * 通过二分查找，找到要插入的位置，然后将数字插入
     * @param nums
     * @param target
     */
    public static void method(List<Integer> nums,int target){

        int len = nums.size();
        int begin = 0;
        int end = len - 1;
        int mid = (begin + end)/2;

        //如果插入值小于或等于第一个元素
        if(target <= nums.get(begin)){
            nums.add(0,target);
            return;
        }
        //如果插入值大于或等于最后一个元素
        if(target >= nums.get(end) ){
            nums.add(target);
            return;
        }

        //插入值的大小在中间的某个位置
        //设置flag判断是否找到了插入的位置
        boolean flag = false;
        //设置插入位置
        int index = 0;
        while (true){
            //如果插入数介于nums[mid]和nums[mid-1]之间，则将这个数插入到mid位置
            if(nums.get(mid) >= target && nums.get(mid - 1) <= target){
                nums.add(mid,target);
                return;

            }else if(target < nums.get(mid)){
                end = mid - 1;
            }else{
                begin = mid + 1;
            }
            mid = (begin + end)/2;
        }


    }
}