leetcode35.搜索插入位置

题目描述

/**
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
     * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     * <p>
     * 你可以假设数组中无重复元素。
     */
         

思路分析：

1. 看到要查找数组中的元素值，新手考虑到的肯定是遍历查找，及暴力查找，而有经验的程序员考虑到的则是二分查找，时间复杂度为O（log n）,

2. 如果是查找目标元素，可以直接使用二分查找，但是题目还要求如果查找的元素不存在，则返回顺序插入的索引

3. 若是查找目标元素，则标间为 nums [i] == target, 若加上顺序索引，则条件为 nums[i] < target < nums[i + 1]

4. 所以综合考虑，只需要满足 target <= nums[i]即可，仍然可以使用二分查找

5. 需要考虑 target大于 数组中所有元素的情况

源码及分析

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

        //可以考虑使用二分查找
        //定义左右两个指针left 和 right
        //用一个变量保存数组的长度，在下次使用数组长度时直接调用这个变量，
        // 可以减少计算的时间，增加程序的高效性
        int len = nums.length;
        //定义index保存要返回的索引值，
        // 将数组的长度直接赋值给index，可以减少target大于数组最大值的一次判断
        //否则要判断target是否大于数组中最大值
        int index = len;
        int left = 0;
        int right = len - 1;
        while (left <= right){
            //定义mid为左右索引之间的中间值
            int mid = (right - left) / 2 + left;
            //如果目标值小于数组元素的中间值，则将右指针置为mid - 1
            if (target <= nums[mid]){
                right = mid - 1;
                index = mid;
                //如果目标值大于数组元素的中间值
            }else {
                left = mid + 1;
            }

        }
        return index;