Index of First 1 in a Sorted Array of 0s and 1s

Problem

Given a sorted array consisting 0s and 1s. The task is to find the index of first 1 in the given array.

NOTE: If one is not present then, return -1.

Examples:

Example 1:

Input : 
arr[] = {0, 0, 0, 0, 0, 0, 1, 1, 1, 1}
Output : 
6
Explanation:
The index of first 1 in the array is 6.

Example 2:

Input : 
arr[] = {0, 0, 0, 0}
Output : 
-1
Explanation:
1's are not present in the array.

Your task:

You don't need to read input or print anything. Your task is to complete the function firstIndex() which takes the array A[] and its size N as inputs and returns the index of first 1. If 1 is not present in the array then return -1.

• Expected Time Complexity: $O(Log (N))$
• Expected Auxiliary Space: $O(1)$

Constraints:

• $1<=N<=10^6$
• $0<=A_i<=1$

Solution

Python

def firstIndex(self, arr, n):
    low = 0
    high = n - 1
    first_one_index = -1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == 1:
            first_one_index = mid
            high = mid - 1  
        else:
            low = mid + 1   
    return first_one_index

Java

public long firstIndex(long arr[], long n) {
    long low = 0;
    long high = n - 1;
    long firstOneIndex = -1;
    while (low <= high) {
        long mid = (low + high) / 2;
        if (arr[(int)mid] == 1) {
            firstOneIndex = mid;
            high = mid - 1; 
        } 
        else {
            low = mid + 1; 
        }
    }
    return firstOneIndex;
}

C++

int firstIndex(int a[], int n) {
    int low = 0;
    int high = n - 1;
    int firstOneIndex = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == 1) {
            firstOneIndex = mid;
            high = mid - 1; 
        } 
        else {
            low = mid + 1; 
        }
    }
    return firstOneIndex;
}

C

int firstIndex(int a[], int n) {
    int low = 0;
    int high = n - 1;
    int firstOneIndex = -1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (a[mid] == 1) {
            firstOneIndex = mid;
            high = mid - 1; 
        } 
        else {
            low = mid + 1; 
        }
    }
    return firstOneIndex;
}

• Time Complexity: $O(Log (N))$
• Auxiliary Space: $O(1)$