力扣35-搜索插入位置——二分查找

题目描述

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

请必须使用时间复杂度为 O(log n) 的算法。

解题思路

• 这也是一道查找元素的题目，题目要求是在有序数组查找元素并返回索引；
• 如果元素不在数组中应该返回他本应该的索引位置；

• 

•  那么目标值有可能就有四种情况：①比第一个元素还小，放在数组最前面；②比最后一个元素大，插在数组尾部；③等于数组中某个值，返回索引；④在数组中未找到这个值，找合适的位置将其插入
• 可以想到这种题目应该要用二分法求解；
• 在开始判断target与数组首末元素的大小关系，并返回正确的索引；
• 在查找过程中采用左右闭合的区间 [ left ,  right ]；
• 只是在判断完所有的情况时，不应该返回-1，应该返回 right+1,因为 right+1 是此时要插入位置的索引。

输入输出示例

 

代码

class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n-1;
        //boolean flag = false;
        if(target < nums[0]){
            return 0;
        }else if(target > nums[n-1]){
            return n;
        }
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(target == nums[mid]){
                //flag = true;
                return mid;
            }else if(target< nums[mid]){
                //flag = true;
                right = mid - 1;
            }else if(target > nums[mid]){
                //flag = true;
                left = mid + 1;
            }
        }
        return right+1;
    }
}