LeetCode__35.搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0

题解

典型的二分查找了(什么是二分查找？点这)，首先快速得出两种情况，当 target < nums[0] 和 target > nums[length - 1];分别返回 0 或者 length就行
当不满足就进行二分查找，当找不到时，直接返回left就行

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

大功告成