top of page

Looking to master object-oriented and system design for tech interviews or career growth?

  • Improve your system design and machine coding skills.

  • Study with our helpful resources.

  • Prepare for technical interviews and advance your career.

**We're in beta mode and would love to hear your feedback.

Search for a Range InterviewBit Solution


Problem Description:

Given a sorted array of integers A(0 based index) of size N, find the starting and ending position of a given integer B in array A.

Your algorithm’s runtime complexity must be in the order of O(log n).

Return an array of size 2, such that first element = starting position of B in A and second element = ending position of B in A, if B is not found in A return [-1, -1].


Input Format

The first argument given is the integer array A. The second argument given is the integer B. 

Output Format

 Return an array of size 2, such that first element = starting position of B in A and second element = ending position of B in A, if B is not found in A return [-1, -1]. 

Constraints

1 <= N <= 10^6 
1 <= A[i], B <= 10^9 

For Example

Input 1:
    A = [5, 7, 7, 8, 8, 10]
    B = 8
Output 1:
    [3, 4]
Explanation 1:
    First occurence of 8 in A is at index 3
    Second occurence of 8 in A is at index 4
    ans = [3, 4]

Input 2:
    A = [5, 17, 100, 111]
    B = 3
Output 2:
    [-1, -1]


Approach


The solution is to about finding the lower bound and upper bound of the given element.

So we can use two binary search algorithm for each one to find out our desired result.



Time & Space Complexity

Time Complexity: O(LogN)

- Since we have used a binary search algorithm.

Space Complexity: O(1)

- Ignoring space taken by input array.



Solution


Code in C++


Comments


bottom of page