Question

DO NOT CHANGE THE METHOD HEADER

Write a method

int indexFirstOne (int [] input)

The input array is sorted and every element is 0 or 1. Return the index of the first 1. If there are no 1s in the array, return -1. The worst case runtime must be O(logn) where n is the number of elements.

Example a = [0, 0, 1, 1, 1] return 2

Answer 1

// C++ program

#include <bits/stdc++.h>

using namespace std;

int binarySearch(int a[], int left, int right, int key)

{

if (right < left)

return -1;

int mid = left + (right - left) / 2; //calculate mid

if (a[mid] == key) //element found

return mid;

if (a[mid] > key)

return binarySearch(a, left, mid - 1, key); //check left sub array

return binarySearch(a, mid + 1, right, key); //check right sub array

}

int indexFirstOne(int a[])

{

int n = 5; // size of array

int index = binarySearch(a, 0, n - 1, 1); //find index of 1 by binary search in array

// element not found

if (index == -1)

return -1; //return -1

int left = index - 1;

while (left >= 0 && a[left] == 1) //find element on left side of this index, if more 1 exist to get index of leftmost 1

left--;

return left+1; //return leftmost index

}

int main()

{

int a[] = {0,0,1,1,1};

cout << indexFirstOne(a);

return 0;

}