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: ```text 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: ```text 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: ```text nums = [0, 1, 0, 3, 12] After modification: [1, 3, 12, 0, 0] ```