# Find Transition Point

Last updated: 6th Sep, 2020

### Problem Statment

You are given a sorted array containing only numbers 0 and 1. Find the transition point efficiently. The transition point is a point where "0" ends and "1" begins (0 based indexing).
Note:

- If there is no "1" exists, print -1.
- In case of all 1s print 0.

Expected Time Complexity: O(LogN).
Expected Auxiliary Space: O(1).

#### Input

The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows. First Line of each test case contains N (number of elements in array). Second line contains N space seperated integers.

#### Output

Print Transition point or -1 for all 0s and 0 for all 1s.

Example 1:

    Input:
    1
    5
    0 0 0 1 1
    Output:
    3

Example 2:

    Input:
    1
    4
    0 0 0 0
    Output:
    -1

### Naive Approach(Iterative):

We can traverse the array and return the index of first 1 we find.
Time Complexity: O(N)
Space Complexity: O(1)

#### Pseudo Code

function transitionPoint(Argument givenArray){

- traverse the array from start to end:
- - Check if the current element is '1'
    - IF Yes:
      - Return index
      - Break loop
    - IF No:
      - Keep Traversing
- Print Index of First 1

}

##### C++ Function Implementation

    int transitionPoint(int arr[], int n) {
        for(int i = 0 ; i < n ; i++){
    		if(arr[i] == 1){
    	  		return i;
    		}
    	}
        return -1;
    }

#### Optimised Approach

We will use binary search on sorted array to find smallest index of 1 in array.

##### Pseudo Code

function transitionPoint(Argument givenArray) {

- For Binary Search create two integer variables 'l' and 'u'
- initialize l = 0 and u = n - 1
- Search while l <= u:
  - Create a mid Integer variable and initialize mid = (l + u)/2
  - Check if the element at mid index is 1
    - IF Yes:
      - Check if it is smallest index of 1
        - IF Yes:
          - Return Index
        - IF No:
          - Update u = mid - 1
    - IF No:
      - Update l = mid + 1
- Return -1

}

##### C++ Function Implementation

    int transitionPoint(int arr[], int n)
    {
        int l = 0, u = n-1;

        while (l <= u)
        {
            int mid = (l + u)/2;

            if (arr[mid] == 0)
                l = mid+1;

            else if (arr[mid] == 1)
            {
                if (arr[mid-1]==0)
                    return mid;

                u = mid-1;
            }
        }
        return -1;
    }

##### Program Code

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

    //-------------- Naive Approach-----------------

    /*

    int transitionPoint(int arr[], int n) {
        for(int i = 0; i < n; i++){
    		if(arr[i] == 1 ){
    	  		return i;
    		}
    	}

        return -1;
    }

    */

    // ------------- Optimised Approach-------------------

    int transitionPoint(int arr[], int n)
    {
        int l = 0, u = n-1;

        while (l <= u)
        {
            int mid = (l + u)/2;

            if (arr[mid] == 0)
                l = mid+1;

            else if (arr[mid] == 1)
            {
                if (arr[mid-1]==0)
                    return mid;

                u = mid-1;
            }
        }
        return -1;
    }
    int main() {
        int t;
        cin >> t;
        while (t--) {
            int n;
            cin >> n;
            int a[n], i;
            for (i = 0; i < n; i++) {
                cin >> a[i];
            }
            cout << transitionPoint(a, n) << endl;
        }
        return 0;
    }