Find First and Last Position of Element in Sorted Array

class Solution {
public:
    vector<int> findFirstAndLast(vector<int>& nums, int target) {
        int lowerBound = findPosition(nums, target, true);
        if (lowerBound == -1) {
            return vector<int>{-1, -1};
        }
        int upperBound = findPosition(nums, target, false);
        return vector<int>{lowerBound, upperBound};
    }

private:
    int findPosition(vector<int>& nums, int value, bool findFirst) {
        int size = nums.size();
        int start = 0, end = size - 1;
        while (start <= end) {
            int middle = (start + end) / 2;
            if (nums[middle] == value) {
                if (findFirst) {
                    if (middle == start || nums[middle - 1] != value) {
                        return middle;
                    }
                    end = middle - 1;
                } else {
                    if (middle == end || nums[middle + 1] != value) {
                        return middle;
                    }
                    start = middle + 1;
                }
            } else if (nums[middle] > value) {
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        return -1;
    }
};

This solution in C++ provides an efficient method to find the first and last position of a given element in a sorted array. The algorithm effectively utilizes the concept of binary search to locate the desired positions, ensuring a time complexity of O(log n), thereby optimizing the search process in large datasets.

The process encapsulated in the findFirstAndLast function involves:

1. Determining the lower bound of the target using the findPosition function with findFirst set to true. If the target isn't found (indicated by -1), the function instantly returns {-1, -1}.
2. If the lower bound is found, it proceeds to find the upper bound, again using the findPosition function but with findFirst set to false.

The findPosition function incorporates a binary search technique, adjusting start and end indexes based on comparisons with the target:

• If findFirst is true and the target matches nums[middle], the function checks if it's the first occurrence. If middle matches start or the previous element is not the target, the position is confirmed.
• If looking for the last occurrence (findFirst false), similar logic applies but checks if the found position is the last occurrence of the target.
• The usual binary search adjustments of either narrowing down from the start or the end of the array continue until the target is located or until the search space is exhausted.

The encapsulation into a private function for the repetitive process of locating positions reduces redundancy and enhances clarity, making the code modular and easier to troubleshoot. This implementation ensures robust handling of edge cases such as not finding the target or the target existing at the boundaries of the array. All operations focus on efficiency and clarity, adhering closely to the principles of structured, modular design.

class Solution {
    public int[] findFirstAndLastPosition(int[] numbers, int targetValue) {
        int lowerBound = this.determinePosition(numbers, targetValue, true);

        if (lowerBound == -1) {
            return new int[] { -1, -1 };
        }

        int upperBound = this.determinePosition(numbers, targetValue, false);

        return new int[] { lowerBound, upperBound };
    }

    private int determinePosition(int[] numbers, int targetValue, boolean isLower) {
        int length = numbers.length;
        int start = 0, finish = length - 1;

        while (start <= finish) {
            int midPoint = (start + finish) / 2;

            if (numbers[midPoint] == targetValue) {
                if (isLower) {
                    if (midPoint == start || numbers[midPoint - 1] != targetValue) {
                        return midPoint;
                    }
                    finish = midPoint - 1;
                } else {
                    if (midPoint == finish || numbers[midPoint + 1] != targetValue) {
                        return midPoint;
                    }
                    start = midPoint + 1;
                }
            } else if (numbers[midPoint] > targetValue) {
                finish = midPoint - 1;
            } else {
                start = midPoint + 1;
            }
        }

        return -1;
    }
}

This Java solution defines a method to find the first and last positions of a given element in a sorted array. It uses binary search to efficiently locate the positions, optimizing the search process when the element is found or confirming its absence.

• The method findFirstAndLastPosition initializes the search for both bounds using another method determinePosition.
• The determinePosition method conducts the binary search. By passing a boolean parameter, it adjusts the search dynamically for the lower or upper bound.

Detailed Explanation of the Method:

1. Start by initializing lowerBound using determinePosition method configured to find the lower boundary.
2. If lowerBound is -1 (target value not found), immediately return {-1, -1}.
3. If the target value is present, upperBound is determined using the same determinePosition method configured for finding the upper boundary.
4. Finally, return the positions as an array: {lowerBound, upperBound}.

Within determinePosition:

1. The method establishes a binary search loop adjusting start and finish pointers based on comparisons.
2. Adjust the pointers based on whether the search is for the lower or upper bound when the target is equal to the middle value:
   • For the lower bound, verify that the preceding item is different.
   • For the upper bound, check that the following item is not the target.
   • Adjust the respective pointers accordingly (start or finish) to narrow the search.
3. Continue adjusting the boundaries (start and finish) until the target is found or the bounds invalidate the loop.
4. Return either the position of the target or -1 if it isn't found during the adjustments.

This efficient binary search approach ensures the solution remains optimal even for large arrays, with its runtime complexity being O(log n) due to the binary search properties.

int locatePosition(int* array, int arrayLength, int value, int isLowest) {
    int start = 0, finish = arrayLength - 1;
    while (start <= finish) {
        int middle = (start + finish) / 2;
        if (array[middle] == value) {
            if (isLowest) {
                if (middle == start || array[middle - 1] != value) {
                    return middle;
                }
                finish = middle - 1;
            } else {
                if (middle == finish || array[middle + 1] != value) {
                    return middle;
                }
                start = middle + 1;
            }
        } else if (array[middle] > value) {
            finish = middle - 1;
        } else {
            start = middle + 1;
        }
    }
    return -1;
}
int* searchExtremes(int* array, int arrayLength, int value, int* returnedSize) {
    int* extremities = malloc(sizeof(int) * 2);
    int lowestOccurrence = locatePosition(array, arrayLength, value, 1);
    if (lowestOccurrence == -1) {
        extremities[0] = -1;
        extremities[1] = -1;
        *returnedSize = 2;
        return extremities;
    }
    int highestOccurrence = locatePosition(array, arrayLength, value, 0);
    extremities[0] = lowestOccurrence;
    extremities[1] = highestOccurrence;
    *returnedSize = 2;
    return extremities;
}

The provided C code defines a solution for finding the first and last positions of a specific element in a sorted array. The solution utilizes two primary functions:

1. locatePosition: This function is designed to find either the lowest or highest index of the specified element (value) in the array. The function takes the complete array, its arrayLength, the value to find, and a boolean isLowest to determine if you are looking for the lowest or highest index.

   • It initializes start to the beginning of the array and finish to the end.
   • A binary search is performed within the while loop. Depending on whether isLowest is true or false, the index gets adjusted to either keep searching to the left (to find the first occurrence) or right (to find the last occurrence).
   • If the element is found at the calculated mid index and conditions for being the lowest or highest are met, it returns the index.
   • If the desired element is not found in the range, it returns -1.

2. searchExtremes: This function utilizes the locatePosition function to find both the first and last occurrences of an element.

   • It initially allocates memory for an array extremities to store the results.
   • Calls locatePosition twice with isLowest set to true for the first call and false for the second call, effectively finding the lowest and highest occurrences of value.
   • Stores these indices in extremities.
   • Sets returnedSize (likely intended as output to indicate the size of extremities) to 2.
   • Returns extremities, which contains the first and last positions of the element. If the element is not found at all, both positions are set to -1.

This solution effectively implements a modified binary search and memory management using malloc, making it efficient for large arrays. Moreover, it robustly handles cases where the target value might not be present in the array. This approach is key in scenarios where performance is critical, and handling non-existent values gracefully is essential.

var findTargetRange = function (elements, targetValue) {
    const initialIndex = locateBound(elements, targetValue, true);
    if (initialIndex == -1) {
        return [-1, -1];
    }
    const finalIndex = locateBound(elements, targetValue, false);
    return [initialIndex, finalIndex];
    function locateBound(elements, targetValue, isStarting) {
        let length = elements.length;
        let start = 0,
            end = length - 1;
        while (start <= end) {
            let middle = Math.floor((start + end) / 2);
            if (elements[middle] == targetValue) {
                if (isStarting) {
                    if (middle == start || elements[middle - 1] != targetValue) {
                        return middle;
                    }
                    end = middle - 1;
                } else {
                    if (middle == end || elements[middle + 1] != targetValue) {
                        return middle;
                    }
                    start = middle + 1;
                }
            } else if (elements[middle] > targetValue) {
                end = middle - 1;
            } else {
                start = middle + 1;
            }
        }
        return -1;
    }
};

The JavaScript function findTargetRange finds the first and last positions of a specified element within a sorted array. This is particularly useful when dealing with duplicates in the array and needing to ascertain the range of indices for a specific target value.

Following is a breakdown of the process:

• Use the function locateBound for locating the desired indices. This nested function accepts three parameters: elements for the array, targetValue for the element to find, and isStarting to determine if searching for the start or end index.

• The locateBound function initializes with start and end set to the boundaries of the array and employs a binary search mechanism. If the middle element matches the targetValue:

  • When searching for the start index (isStarting is true), check if it is the first occurrence of targetValue. If not, adjust the end to tighten the search space.

  • When searching for the end index (isStarting is false), verify if the found index is the last occurrence. If not, adjust the start to refine the search range.

• The function findTargetRange initially invokes locateBound to search for the starting index. If no such index exists, it returns [-1, -1] indicating the absence of targetValue.

• If the starting index is found, locateBound is called again to locate the final index, using the previously located starting point.

This approach ensures an efficient search with a complexity of O(log n), which is optimal for sorted arrays. The resultant indices of the first and last occurrence of the target element are then returned as an array. This detailed and precise method leverages binary search principles tailored for sorted arrays, making it efficient and effective for frequent and varied applications.

class Solution:
    def locateRange(self, arr: List[int], key: int) -> List[int]:

        first_index = self.findIndex(arr, key, True)
        if first_index == -1:
            return [-1, -1]

        last_index = self.findIndex(arr, key, False)

        return [first_index, last_index]

    def findIndex(self, arr: List[int], key: int, isStart: bool) -> int:

        length = len(arr)
        low, high = 0, length - 1
        while low <= high:
            mid = int((low + high) / 2)

            if arr[mid] == key:

                if isStart:
                    if mid == low or arr[mid - 1] < key:
                        return mid
                    high = mid - 1
                else:
                    if mid == high or arr[mid + 1] > key:
                        return mid
                    low = mid + 1

            elif arr[mid] > key:
                high = mid - 1
            else:
                low = mid + 1

        return -1

The Python solution aims to find the first and last position of a given element in a sorted array. The solution comprises two main methods within the Solution class:

• locateRange: This method calls the helper function findIndex twice. Once to find the first occurrence of the key and once to find the last occurrence. If the findIndex method returns -1 for the first occurrence, the function immediately returns [-1, -1], indicating that the key is not present. If the key exists, it proceeds to find the last index.

• findIndex: This method uses a binary search approach to find an index based on whether the search is for the first or last occurrence of the key identified by the isStart boolean. When isStart is true, the function searches for the first occurrence of the key. If isStart is false, the function looks for the last occurrence. If the key is found based on the condition specified (first or last), the respective index is returned. If the key doesn't exist at all, the method returns -1.

Here's what happens step-by-step:

1. Define the locateRange method to manage the flow and handle cases where the key might not be present.
2. Define findIndex method to apply a binary search for detecting either the first or last index of the key.
3. Apply conditions in the binary search logic to ensure the correct occurrence (first or last) is accurately determined and returned.

By integrating binary search, the solution efficiently narrows down the search space, ensuring a time complexity of O(log n), which is optimal for sorted arrays.

This approach emphasizes clarity and efficiency by segregating the search logic into a dedicated method (findIndex) and using locateRange to handle the search outcome and edge cases. This modular structure also makes the code easier to manage and debug.