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

題目描述

給定一個(gè)排序數(shù)組和一個(gè)目標(biāo)值，在數(shù)組中找到目標(biāo)值，并返回其索引。如果目標(biāo)值不存在于數(shù)組中，返回它將會被按順序插入的位置。
請必須使用時(shí)間復(fù)雜度為 O(log n) 的算法。

題目分析

根據(jù)題目要求本題『請必須使用時(shí)間復(fù)雜度為 O(log n) 的算法』,可想到二分查找。

代碼實(shí)現(xià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;


    }


}

復(fù)雜度

• 時(shí)間復(fù)雜度：O(logn)，其中 n 是定版本的數(shù)量。
• 空間復(fù)雜度：O(1)，只需要常數(shù)的空間保存變量。

好了，今天就到這里，感謝各位看官到這里，不如點(diǎn)個(gè)關(guān)注吧！