This week's practice focuses on mastering binary search algorithms through LeetCode problems.

The first problem is Binary Search. Below is the implementation:

int search(int* nums, int numsSize, int target) {
    int left = 0;
    int right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target)
            return mid;
        else if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }

    return -1;
}

Another variant of this problem is Search Insert Position. Here's an alternative solusion using a linear scan:

int searchInsert(int* nums, int numsSize, int target) {
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] >= target)
            return i;
    }
    return numsSize;
}

A more optimized version using binary search is shown below:

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        return left;
    }
};

For Find First and Last Position of Element in Sorted Array, we can use two binary searches to locate the boundaries:

int searchBoundary(int* nums, int numsSize, int target, bool isLeft) {
    int left = 0, right = numsSize - 1, ans = numsSize;

    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] > target || (isLeft && nums[mid] >= target)) {
            right = mid - 1;
            ans = mid;
        } else {
            left = mid + 1;
        }
    }

    return ans;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int* ret = malloc(sizeof(int) * 2);
    memset(ret, -1, sizeof(ret));
    *returnSize = 2;

    int l = searchBoundary(nums, numsSize, target, true),
        r = searchBoundary(nums, numsSize, target, false) - 1;

    if (l != numsSize && nums[l] == target)
        ret[0] = l, ret[1] = r;

    return ret;
}

An efficient approach involves separate functions for finding left and right boundaries:

int findLeftBound(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid - 1;
        else
            right = mid - 1;
    }

    if (left < 0 || left >= numsSize)
        return -1;

    return nums[left] == target ? left : -1;
}

int findRightBound(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid - 1;
        else
            left = mid + 1;
    }

    if (right < 0 || right >= numsSize)
        return -1;

    return nums[right] == target ? right : -1;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * 2);
    res[0] = findLeftBound(nums, numsSize, target);
    res[1] = findRightBound(nums, numsSize, target);
    *returnSize = 2;
    return res;
}

In Sqrt(x), binary search is used to find the integer square root:

int mySqrt(int x) {
    int left = 0, right = x, ans = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if ((long long)mid * mid <= x) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return ans;
}

For Valid Perfect Square, one can also use a mathematical property involving odd numbers:

bool isPerfectSquare(int num) {
    int odd = 1;
    while (num > 0) {
        num -= odd;
        odd += 2;
    }
    return num == 0;
}

Alternatively, a binary search approach can be applied:

bool isPerfectSquare(int num) {
    int left = 0, right = num;
    while (left <= right) {
        int mid = (right - left) / 2 + left;
        long square = (long)mid * mid;
        if (square < num)
            left = mid + 1;
        else if (square > num)
            right = mid - 1;
        else
            return true;
    }
    return false;
}

It's crucial to memorize the binary search framework and distinguish between closed intervals [left, right] and half-open intervals [left, right). Exploring variations of binary search will further enhance understanding.