Leecode 35 ----- 搜索插入位置

Leecode 35 ----- 搜索插入位置

题目描述

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

思路

二分查找
时间复杂度:O(log n)在这里插入代码片
左侧下标 left = 0;
右侧下标 right = 0;
判断:while (left <= right)

  • 中间下标 mid = (left + right) / 2
  • 比较nums[mid] 和 target 的大小
    • 相等,返回 mid 下标,return mid
    • nums[mid] < target,left = mid + 1
    • nums[mid] > target,right = mid - 1

return left;

实现

/**
 * Author: lisiyu
 * Created: 2020/1/20
 */
    // 二分查找
public class SearchInsert35 {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        if (nums.length == 0) {
            return 0;
        }
        if (nums[nums.length - 1] < target) {
            return nums.length;
        }

        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
Leecode 35 ----- 搜索插入位置Leecode 35 ----- 搜索插入位置 鱼语雨06 发布了32 篇原创文章 · 获赞 0 · 访问量 855 私信 关注
上一篇:leeCode 278


下一篇:LeeCode_反转字符串中的元音字符