How to use Advanced Binary Scarch ?

Why and how ?

while i was solving the question on leetcode which says in an Given array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value. so it was impossible to return the starting and ending of a target element in an array with simple binary scarch because it only returns the index where it found the first target element that can be anything first , end or middle of that element. so we use Double Binary Scarch , and here's how to do it ...

Approach

1. First Binary Search:

   • Perform a binary search to find the last occurrence of the target.
   • Start with si (start index) at 0 and ei (end index) at nums.length - 1.
   • If the middle element nums[mid] is less than the target, move the start index si to mid + 1 to search in the right half.
   • If it is greater than the target, move the end index ei to mid - 1 to search in the left half.
   • If nums[mid] equals the target, set res[1] to mid (the current end of the range) and continue searching in the right half (si = mid + 1) to find the last occurrence.

2. Second Binary Search:

   • Perform another binary search to find the first occurrence of the target.
   • Reset si to 0 and ei to nums.length - 1.
   • Follow a similar approach as before, but if nums[mid] equals the target, set res[0] to mid (the current start of the range) and continue searching in the left half (ei = mid - 1) to find the first occurrence.

3. Return Result:

   • The result array res contains the starting and ending indices of the target value.

Complexity

• Time Complexity:

  • The binary search for the first and last occurrences each takes O(log n) time. Since we perform two binary searches, the overall time complexity is O(log n).

• Space Complexity:

  • O(1) since we are using a fixed amount of extra space for variables.

Code

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ei = nums.length - 1;
        int si = 0;
        int[] res = {-1, -1};  // Initialize result array

        // First binary search to find the last occurrence
        while (si <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > nums[mid]) {
                si = mid + 1;
            } else {
                res[1] = mid;  // Update end index
                si = mid + 1;  // Search in the right half
            }
        }

        // Reset the pointers for the second binary search
        si = 0;
        ei = nums.length - 1;

        // Second binary search to find the first occurrence
        while (si <= ei) {
            int mid = si + (ei - si) / 2;
            if (target < nums[mid]) {
                ei = mid - 1;
            } else if (target > nums[mid]) {
                si = mid + 1;
            } else {
                res[0] = mid;  // Update start index
                ei = mid - 1;  // Search in the left half
            }
        }

        return res;  // Return the result array
    }
}

The above is the detailed content of How to use Advanced Binary Scarch ?. For more information, please follow other related articles on the PHP Chinese website!