https://leetcode-cn.com/problems/search-insert-position

一 题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1: 输入: nums = [1,3,5,6], target = 5

输出: 2

示例 2: 输入: nums = [1,3,5,6], target = 2

输出: 1

示例 3: 输入: nums = [1,3,5,6], target = 7

输出: 4

示例 4: 输入: nums = [1,3,5,6], target = 0

输出: 0

示例 5: 输入: nums = [1], target = 0

输出: 0

提示: 1 <= nums.length <= 104 -104 <= nums[i] <= 104 nums 为无重复元素的升序排列数组

-104 <= target <= 104

二 题解

package top.black.leetcode.s00200.s0035searchInsert;
class Solution {
    public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length-1;
        /*   先解决边界，可去除无效的二分查找比较次数  */
        if(target<nums[start]){
            return 0;
        }else if(target>nums[end]){
            return end+1;
        }
        int tag = 0;
        while(start<end){
            tag = start + (end - start)/2;
            if(target==nums[tag]){
                return tag;
            }else if(target>nums[tag]){
                start = tag+1;
                continue;
            }
            end = tag;
        }
        return start;
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
            //   nums = [1,3,5,6], target = 5
        int[] nums1 = {1,3,5,6};
        System.out.println(solution.searchInsert(nums1,5));//2
        System.out.println(solution.searchInsert(nums1,2));//1
        System.out.println(solution.searchInsert(nums1,7));//4
        System.out.println(solution.searchInsert(nums1,0));//0
        int[] nums2 = {1};
        System.out.println(solution.searchInsert(nums2,0));//0
    }
}