给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 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
Related Topics
  • 数组
  • 二分查找
  • \n
  • 👍 948
  • 👎 0
  • 题解

    把头尾情况单独处理了去掉,剩下的用二分法无限逼近目标位置,得到left的值

    之后再再小区间内做个遍历循环,二分法本身应该是有办法可以取到准确的目标位置的,但是这个里面边界判断的情况实在是有点头疼,于是就取个巧,最终位置无限逼近之后,再前后扩展一位进行大小判断

    
    
    
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public static int searchInsert(int[] nums, int target) {
            //请在此作答
            if(null==nums || nums.length == 0 || target < nums[0] || nums[0] == target){
                return 0;
            }
            if (nums[nums.length-1] == target){
                return nums.length-1;
            }
            if (nums[nums.length-1] < target){
                return nums.length;
            }
            int left = 0;
            int right = nums.length-1;
    
            while (left < right){
                int mid = left + (right-left)/2;
                if (nums[mid] == target){
                    return mid;
                }
                if (nums[mid] > target){
                    right = mid-1;
                }else{
                    left = mid+1;
                }
    
            }
            for (int i = left-1; i <= left+1; i++) {
                if (i<0 || i>= nums.length){
                    continue;
                }
                if (nums[i] == target){
                    return i;
                }
                if (nums[i] < target && nums[i+1] > target){
                    return i+1;
                }
            }
    
            return left;
    
    
    
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)