在给定的一维已排序（升序）数组中寻找插入一个元素的位置

在给定的一维已排序（升序）数组中寻找插入一个元素的位置

在给定的一维已排序（升序）数组中寻找插入一个元素的位置，返回该元素在数组中的下标值。
如果该元素已经存在于数组中，则直接返回该元素在数组中的下标值。

例如：给定数组 {1，3，4，5，6，9，11}，目标值是 7。
数组中不包含目标值，插入目标之后，数组变为： {1，3，4，5，6，7，9，11}，返回下标值：5。

再例如：给定数组 {1，3，4，5，6，9，11}，目标值是 5。
数组中包含目标值，返回下标值：3。

算法设计

public static int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length;
        while(low < high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] < target)
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }

完整测试代码如下：

采用二分查找思路。

package com.bean.algorithmbasic;

public class SearchInsertPosition {

    public static int searchInsert(int[] nums, int target) {
        int low = 0, high = nums.length;
        while(low < high) {
            int mid = low + (high - low) / 2;
            if(nums[mid] < target)
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] array= {1,3,4,7,15,19,22,25};
        //int target=10;
        int target=3;
        int ANSWER=searchInsert(array,target);
        System.out.println("ANSWER = "+ANSWER);
    }

}

运行结果

ANSWER = 1

（完）