Implement Sorted Search and Array Updates

Implement the following independent array functions.

Part 1: Search a sorted array

Given a sorted array of integers nums in nondecreasing order and an integer target, return the index of target if it exists. If target does not exist, return -1.

Requirements:

• The algorithm should run in O(log n) time.
• If there are duplicate values equal to target, returning any valid index is acceptable.

Example:

nums = [1, 3, 5, 7, 9], target = 7
Output: 3

Part 2: Add one to an integer represented as digits

You are given an array digits representing a nonnegative integer. Each element is one decimal digit, and the most significant digit is at index 0. Add 1 to the integer and return the resulting digit array.

Requirements:

• Do not convert the entire array into a built-in integer type.
• Correctly handle carry propagation.

Examples:

digits = [1, 2, 3]
Output: [1, 2, 4]

 digits = [9, 9, 9]
Output: [1, 0, 0, 0]

Part 3: Move all zero values to the end

Given an integer array nums, rearrange it in place so that all nonzero elements appear first in their original relative order, followed by all zero values.

Requirements:

• Modify the input array in place.
• Preserve the relative order of nonzero elements.
• Use O(1) extra space.

Example:

nums = [0, 1, 0, 3, 12]
After modification: [1, 3, 12, 0, 0]

Search a Sorted Array

Given a sorted array of integers nums in nondecreasing order and an integer target, return the index of target if it exists in the array. If target does not exist, return -1.

The algorithm must run in O(log n) time. If there are duplicate values equal to target, returning any valid index is acceptable.

Example:

nums = [1, 3, 5, 7, 9], target = 7
Output: 3

Constraints

• 0 <= len(nums) <= 10^5
• nums is sorted in nondecreasing order
• -10^9 <= nums[i], target <= 10^9

Hints

1. Maintain a search window [lo, hi] and repeatedly halve it by comparing the middle element with the target.
2. If nums[mid] < target, the answer must be to the right (lo = mid + 1); if nums[mid] > target, it's to the left (hi = mid - 1).
3. Return mid as soon as nums[mid] == target; if the window empties (lo > hi), return -1.

Plus One (Digit Array)

You are given an array digits representing a nonnegative integer, where each element is one decimal digit and the most significant digit is at index 0. Add 1 to the integer and return the resulting digit array.

Do not convert the entire array into a built-in integer type. Handle carry propagation correctly, including the case where a new leading digit is needed.

Examples:

digits = [1, 2, 3]  -> [1, 2, 4]
digits = [9, 9, 9]  -> [1, 0, 0, 0]

Constraints

• 1 <= len(digits) <= 10^4
• 0 <= digits[i] <= 9
• digits has no leading zeros except the number 0 itself (i.e. [0])

Hints

1. Process digits from the least significant end (the last index) toward the front.
2. If the current digit is less than 9, increment it and you're done -- no further carry.
3. If it's 9, set it to 0 and carry into the next digit. If the carry survives past index 0, prepend a 1 (e.g. [9,9,9] -> [1,0,0,0]).

Move Zeroes

Given an integer array nums, rearrange it in place so that all nonzero elements appear first in their original relative order, followed by all zero values.

Modify the input array in place, preserve the relative order of the nonzero elements, and use O(1) extra space. (Return the array so its final state can be checked.)

Example:

nums = [0, 1, 0, 3, 12]
After modification: [1, 3, 12, 0, 0]

Constraints

• 0 <= len(nums) <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• The rearrangement must happen in place with O(1) extra space

Hints

1. Keep a write pointer (insert_pos) for the next slot that should hold a nonzero value.
2. Scan left to right; each time you see a nonzero, copy it to insert_pos and advance insert_pos -- this preserves nonzero order.
3. After the scan, every index from insert_pos to the end should be set to 0.