Search for a Range

Search for a Range: Here, we are going to see a variation of binary search problem which can be featured in any interview problem to be done less than O(n) time complexity.
Submitted by Radib Kar, on June 18, 2020

Problem statement:

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in order to less than O(n).

If the target is not found in the array, return [-1, -1].

Constraints:

1 <= t <= 100
1 <= n <= 1000000

Example:

Test case 1:
Input: 
arr = [5,6,7,8,8,10]
target = 8

Output: 
range is : [3, 4]

Test case 2:
Input: 
arr = [5,7,7,8,8,10]
target = 6

Output:
range is: [-1,-1]

Explanation:

Though the above solutions are self-explanatory,
still for the first test case,

For the first test case,
Target is first present at index 3 and 
last one at 4. (0-based indexing)

For the second test case,
Target is not at all present and 
hence range is [-1,-1]

Solution approach

It's quite similar to binary search. The modification is to not to stop when you get the target find. Search for the upper and lower elements to check if they are the same or not.

Here goes the full algorithm,

  1. Initialize the result range to be [-1,-1]
  2. If array size is 0
    return result;
  3. Initialize left = 0, right = n-1;
  4. while(left<=right)
        mid=(left+right)/2;
        if(nums[mid]==target) //once found search for range
            set i=mid;
            set j=mid;
            while(i>=left && nums[i]==target)
                Decrease i;
            while(j<=right && nums[j]==target)
                Increase j;
            Result is [i+1,j-1]            		
        else if(nums[mid]<target)
            left=mid+1;
        else
            right=mid-1;
        end if
    End while
    
  5. Result stores the starting and ending point of range. If target is not found then the range will be the initial one, [-1,-1]
Let's solve with the first test case,

left = 0
right = 5
mid = 2
a[mid]<target, left = mid+1 = 3

a[mid] == target
so traverse left and right from this
range found to be [3,4]

For the second test case,
It simple comes out of the loop

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

vector<int> searchRange(vector<int>& nums, int target)
{
    int n = nums.size();
    
    vector<int> p(2, -1);
    
    if (n == 0)
        return p;
    
    int left = 0, right = n - 1;
    int mid;
    
    while (left <= right) {
        mid = (left + right) / 2;
        if (nums[mid] == target) { //once found search for range
            int i = mid;
            int j = mid;
            while (i >= left && nums[i] == target)
                i--;
            while (j <= right && nums[j] == target)
                j++;
            p[0] = i + 1;
            p[1] = j - 1;
            return p;
        }
        else if (nums[mid] < target)
            left = mid + 1;
        else
            right = mid - 1;
    }
    return p;
}

int main()
{
    int t;
 
    cout << "Enter number of testcases\n";
    cin >> t;
 
    while (t--) {
        int n;
        
        cout << "Enter length of array\n";
        cin >> n;
        
        cout << "Enter the sorted vector\n";
        vector<int> arr(n);
        for (int i = 0; i < n; i++)
            cin >> arr[i];
        
        int k;
        
        cout << "Enter target no\n";
        cin >> k;
        
        vector<int> result = searchRange(arr, n);
        cout << "range is: [" << result[0] << "," << result[1] << "]\n";
    }
    
    return 0;
}

Output:

Enter number of testcases
2
Enter length of array
6
Enter the sorted vector
5 6 7 8 8 10
Enter target no
8
range is: [3,4]
Enter length of array
6
Enter the sorted vector
5 7 7 8 8 10
Enter target no
6
range is: [-1,-1]





Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.