InterviewBit Academy is now Scaler!
Learn Tech Skills from Scratch @ Scaler EDGE

Search in Bitonic Array!

Problem Description

Given a bitonic sequence A of N distinct elements, write a program to find a given element B in the bitonic sequence in O(logN) time.


  • A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.

  • Problem Constraints

    3 <= N <= 105

    1 <= A[i], B <= 108

    Given array always contain a bitonic point.

    Array A always contain distinct elements.

    Input Format

    First argument is an integer array A denoting the bitonic sequence.

    Second argument is an integer B.

    Output Format

    Return a single integer denoting the position (0 index based) of the element B in the array A if B doesn't exist in A return -1.

    Example Input

    Input 1:

     A = [3, 9, 10, 20, 17, 5, 1]
     B = 20

    Input 2:

     A = [5, 6, 7, 8, 9, 10, 3, 2, 1]
     B = 30

    Example Output

    Output 1:


    Output 2:


    Example Explanation

    Explanation 1:

     B = 20 present in A at index 3

    Explanation 2:

     B = 30 is not present in A

    NOTE: You only need to implement the given function. Do not read input, instead use the arguments to the function. Do not print the output, instead return values as specified. Still have a doubt? Checkout Sample Codes for more details.
    Start solving Search in Bitonic Array! on Interview Code Editor
    • Hint 1
    • Solution Approach
    • Complete Solution
    Asked In:


    Click here to start solving coding interview questions