No.35数组搜索插入位置做题笔记

//1.暴力法
public static void main(String []args){
    int[] arr = new int[] {1, 3, 5, 6, 8};
    int k = 4;
    System.out.println(array(arr, k));
}
public static int array(int[] arr, int k ){
    for (int i = 0; i < arr.length; i++){
        if (arr[i] >= k){
            return i;
        }
    }
    return arr.length;
}

2.二分法

//二分法
public static int array1(int[] nums, int target){
    int n = nums.length;
    int left = 0;
    int right = n - 1;
    while (left <= right){ //当left == right,区间依然有效
        int middle = left + ((right - left) / 2);// 不应该使用Middle=(left+right)/2这种情况，否则对于大数据来说会产生溢出问题。
        if(nums[middle] > target){
            right = middle - 1; // target在左区间，所以[left，middle - 1]
        }
        else if (nums[middle] < target){
            left = middle + 1; // target在右区间，所以[middle + 1，right]
        }
        else return middle;
    }

    //处理其他四种情况：目标值在数组所有元素之前、目标值等于数组某一个元素、目标值插入数组中的位置，目标值在数组所有元素之后
    return right + 1;
}