Blueming
EL PSY CONGROO
【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

解法1:直接暴力遍历搜索

由于数组已经排序,从头遍历数组,判断大小,当索引指向位置的元素大于等于目标值时,则返回当前索引。

class Solution {
    public int searchInsert(int[] nums, int targer) {
        if(target == 0 || nums.length == 0 || target <= nums[0]) {
            return 0;
        }
        
        int len = nums.length;
        for(int i = 0; i < len; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
    }
}

解法2:二分查找

/*
 * @lc app=leetcode.cn id=35 lang=java
 *
 * [35] 搜索插入位置
 * √ Accepted
 * √ 62/62 cases passed (0 ms)
 * √ Your runtime beats 100 % of java submissions
 * √ Your memory usage beats 88.75 % of java submissions (37.4 MB)
 */
class Solution {
    public int searchInsert(int[] nums, int targer) {
        if(target == 0 || nums.length == 0 || target <= nums[0]) {
            return 0;
        }
        
        int start = 0;
        int end = nums.length;
        int middle;
        while(start <= end) {
            middle = ((end - start) >> 1) + start;
            if (nums[middle] > target) {
                start = middle - 1;
            } else {
                end = middle;
            }
        }
        
        return middle;
    }
}