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 starti…


This content originally appeared on DEV Community and was authored by Arkadipta kundu

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
    }
}


This content originally appeared on DEV Community and was authored by Arkadipta kundu


Print Share Comment Cite Upload Translate Updates
APA

Arkadipta kundu | Sciencx (2024-08-31T09:09:37+00:00) How to use Advanced Binary Scarch ?. Retrieved from https://www.scien.cx/2024/08/31/how-to-use-advanced-binary-scarch/

MLA
" » How to use Advanced Binary Scarch ?." Arkadipta kundu | Sciencx - Saturday August 31, 2024, https://www.scien.cx/2024/08/31/how-to-use-advanced-binary-scarch/
HARVARD
Arkadipta kundu | Sciencx Saturday August 31, 2024 » How to use Advanced Binary Scarch ?., viewed ,<https://www.scien.cx/2024/08/31/how-to-use-advanced-binary-scarch/>
VANCOUVER
Arkadipta kundu | Sciencx - » How to use Advanced Binary Scarch ?. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2024/08/31/how-to-use-advanced-binary-scarch/
CHICAGO
" » How to use Advanced Binary Scarch ?." Arkadipta kundu | Sciencx - Accessed . https://www.scien.cx/2024/08/31/how-to-use-advanced-binary-scarch/
IEEE
" » How to use Advanced Binary Scarch ?." Arkadipta kundu | Sciencx [Online]. Available: https://www.scien.cx/2024/08/31/how-to-use-advanced-binary-scarch/. [Accessed: ]
rf:citation
» How to use Advanced Binary Scarch ? | Arkadipta kundu | Sciencx | https://www.scien.cx/2024/08/31/how-to-use-advanced-binary-scarch/ |

Please log in to upload a file.



There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.

Related Posts