每天一道算法题

LeetCode第35题:搜索插入位置

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

这道题可以直接使用二分查找,如果找到了指定数字则直接返回,到最后right-left == 1的时候,左右也都不等于这个数字,那么久应该插入在left的右边一格即可。

    /**
     * 直接二分查找,找不到放到最后的中间
     */
    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        if (nums[0] >= target) {
            return 0;
        }
        if (nums[right] < target) {
            return right + 1;
        }
        // 二分查找
        while (left < right) {
            int mid = (left + right) / 2;
            // 找到了直接返回
            if (nums[mid] == target) {
                return mid;
            }
            // 只剩2个元素时left不等于目标数则返回left+1,也就是right即可
            if (right - left == 1){
                if (nums[left] == target) {
                    return left;
                }else {
                    return right;
                }
            }
            if (nums[left] <= target & nums[mid] >= target) {
                right = mid;
            }else {
                left = mid;
            }
        }
        return 0;
    }
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容