力扣(LeetCode) -- 算法第三十五题--搜索插入位置

题目：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position/

示例一：

输入: [1,3,5,6], 5
输出: 2

示例二：

输入: [1,3,5,6], 2
输出: 1

示例三：

输入: [1,3,5,6], 7
输出: 4

示例四：

输入: [1,3,5,6], 0
输出: 0

思路一：

循环遍历数组，将数组元素取出对比，题目中提到顺序，从示例中可看出为从小到大，即分为四种情况，目标数比第一个数组中的元素都小，直接返回"0";目标数比数组中所有元素都大，返回数组长度作为目标函数下标;目标数在数组中存在，将数组对应的下标取出；目标数在数组中不存在，但又在数组的范围内，遇到比目标数大的数，将目标数放在这个数前面，即返回这个数的下标。

代码演示：

class Solution {
    public int searchInsert(int[] nums, int target) {
        //循环遍历取出数组元素。
        for (int i = 0; i <= nums.length; i++) {
            //当数组元素大于目标值时，目标值代替原本数组的位置,相等则返回对应下标
            if (nums[i] >= target) {
                return i;
            } else if (nums[nums.length - 1] < target) {
                return nums.length;
            }
        }
        return 0;
    }
}

检查结果：

思路二：

使用二分法，在排序数组中遇到求目标值的，第一反应就是二分法查找目标值，

• 设立左下标和右下标，设立中间值
• 根据中间值在数组中的数值，与目标值比较相等返回中间值，数组值小于目标值左下标右移，数组值大于目标值，右指针左移
• 如果没有查找到对应数组的值，则返回left，left为插入位置

代码演示：

class Solution {
    public int searchInsert(int[] nums, int target) {
        //设立左指针和中间指针
        int left = 0, mid;
        //设立右指针
        int right = nums.length - 1;
        //当左指针超过右指针时结束运行
        while (left <= right) {
            //相加除2获取中间值，相减除2获取长度的一半，四舍五入向下取整
            mid = (int) (right + left) / 2;
            //当中间值等于目标值时，返回中间值
            if (nums[mid] == target) {
                return mid;
                //中间值大于目标值，右指针移动
            } else if (nums[mid] > target) {
                right = mid - 1;
                //中间值小于目标值，左指针移动
            } else if (nums[mid] < target) {
                left = mid + 1;
            }
        }
        return left;
    }

}

检测结果：

感谢你的阅读，不足之处欢迎批评指正！