主題

[LeetCode C#] 35. Search Insert Position - Binary Search

帥氣跳蚤蛋 | 2021-07-11 22:10:31 | 巴幣 0 | 人氣 65

難度: Easy
===========================================================================
說明:
給予已按遞增排序的陣列資料與目標值,若找到目標值則返回index,
若沒有則返回按順序所插入的index,
必須使用時間複雜度為O(log n)的演算法.
===========================================================================
測資1:
Input: nums = [1,3,5,6], target = 5
Output: 2

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

測資3:
Input: nums = [1], target = 0
Output: 0
===========================================================================
條件限制:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums為遞增排序
-10^4 <= target <= 10^4
===========================================================================
解題:
最值觀的就是遍歷陣列進行排序,但有限制時間複雜度為O(log n),故使用Binary Search,
建立左,右,中三個指標
左邊指標由0開始,右邊指標由nums的最後一個index開始,
1.中間指標則由左邊+右邊指標位置除2而得,
2.如果中間指標=目標值,表示已找到目標值,則返回中間指標的位置
3.若中間指標>目標值,則右方指標位置=中間指標位置
4.否則左方指標位置=中間指標位置
5.重複1~4左右指標的位置移位,直到左右指標的位置在隔壁則停止搜索

    public class Solution
    {
        public int SearchInsert(int[] nums, int target)
        {
            int left = 0;   //左邊指標
            int right = nums.Length - 1;    //右邊指標
            int mid = 0;    //中間值

            while(left+1<right)
            {
                mid = left + (right - left) / 2;   //取左與右指標的中間值開始搜索

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

            if (nums[right] < target)   //如果所有值皆比target小 ex:nums = [1,3,5,6], target = 7
                return nums.Length;
            else if (nums[left] >= target)
                return left;
            else
                return right;
        }
    }

創作回應

相關創作

更多創作