来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position/

题目描述

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

题目分析

根据题目要求本题『请必须使用时间复杂度为 O(log n) 的算法』,可想到二分查找。

代码实现

public class SouSuoChaRu_35 {

    public static void main(String[] args) {
        SouSuoChaRu_35 erFenChaZhao_704 = new SouSuoChaRu_35();
        int[] nums = {1, 3, 5, 6};
        int target = 7;
        erFenChaZhao_704.search(nums, target);
    }


    public int search(int[] nums, int target) {
        int leftIndex = 0;
        int rightIndex = nums.length - 1;
        int result = nums.length;

        while (leftIndex <= rightIndex) {

            int midIndex = (rightIndex + leftIndex) / 2;

            if (nums[midIndex] >= target) {
                rightIndex = midIndex - 1;
                result = midIndex;
                System.out.println(result);
            } else {
                leftIndex = midIndex + 1;
            }
        }
        System.out.println("result:" + result);
        return result;


    }


}

复杂度

• 时间复杂度：O(logn)，其中 n 是定版本的数量。
• 空间复杂度：O(1)，只需要常数的空间保存变量。

好了，今天就到这里，感谢各位看官到这里，不如点个关注吧！