검색 삽입 위치

#35.검색 삽입 위치

문제 설명

개별 정수의 정렬된 배열과 대상 값이 주어지면 대상이 발견되면 인덱스를 반환합니다. 그렇지 않은 경우 순서대로 삽입된 인덱스를 반환합니다.

런타임 복잡도O(log n)로 알고리즘을 작성해야 합니다.

예 1

Input: nums = [1,3,5,6], target = 5
Output: 2

예 2

Input: nums = [1,3,5,6], target = 2
Output: 1

예 3

Input: nums = [1,3,5,6], target = 7
Output: 4

설명

給定 給定 個 一 陣列 陣列 和 一 個 目標值 目標值 目標值 目標值 目標值 其中 的 的 元素 不 重複 重複 重複 重複 重複 重複 重複 重複 重複 陣列 中 找到 找到 目標 目標 值 則 則 返回 其 其 索引 索引 索引 不 不 存在 目標 值 值 則 返回 應 應 當 當 當 插入 位置 的 索引 索引 索引 索引 目標

限制解法的時間複雜度為 O(log n)

해결책

由題目給的是已排序陣列,沒有太多想法,直接使用二分搜尋法來解

public int SearchInsert(int[] nums, int target)
{
    int left = 0, right = nums.Length - 1, mid;

    while (left <= right)
    {
        mid = (left + right) / 2;

        if (nums[mid] == target) return mid;
        else if (target > nums[mid]) left = mid + 1;
        else right = mid - 1;
    }

    return left;
}

참조

LeetCode Solution

GitHub Repository


글 읽어주셔서 감사합니다 🌷 🌻 🌼

마음에 드셨다면 주저말고 하트 꾸욱 눌러주세요❤️
또는 내 Leetcode 솔루션에서 좋아요를 클릭하세요.
또는 내 GitHub ⭐ 팔로우
또는 커피를 사주세요 ⬇️ 감사합니다.