CareerCup

I sincerely think it's much helpful to explain the algo than posting some code here.

Yes, I think you can use binary search to solve this problem.

let's say you have 100 0/1 in array. then convert binary to decimal, say k. if k > 1.

then convert first 50 to decimal, check if it is >1.
if it is 0, then convert 51~75

and go on....

you will find first 1 in lgn complexity.

This is a trick question, as it cannot be done in less than O(N).

Proof: Suppose we have an array of all zeros. Obviously we would have to check ALL the elements (and it doesn't matter in which order we do it) to know that there is no "1" element.
Now suppose we put "1" element in the last item we checked in the previous part, and run the algorithm again. It would still need N steps to find the "1" we inserted, since we already know that the item that contains "1" is the last one to be checked.

So we just prooved there is a case that takes O(N) to find the first "1". This means I proved that he problem is O(N) in the worst case.

Edit: Here's some explanation for Jack:

As indicated by the question, we are required to find the answer in O(N) or better time. Thus, sorting is not an option since it takes O(nlogn) time for any comparison based sorting algorithm. Finally, the question hinted to use a binary search meaning to cut things in halves and try to find the first occurring "1".

Typically, a binary search starts by looking at the middle of an array (or the root if it's a binary search tree), and if the middle (or root) is smaller than the item we are looking for, we go right else we go left. By going either direction, we effectively skipped half of the original array (or tree). This operation is O(logn) which is better than O(N).

However, the input is not sorted and so not all items on the left of the middle is smaller than the middle. This means, not all zeros are on the left side of the middle and not all ones are on the right side. This means, without sorting, the worse case is O(N).

Since the question insist on using "binary search", we can try to skip half of the list at a time until we hit a "1" that is on the left most side.

Here's my code in Python (now with comments):

def findOneHelper(bString, start, end):
    #we are on the left most side of the sub-array
    if(start == end):
        #check if this left most index is "1"
        if(bString[start] == "1"):
            return start;
        return -1;
    #calculate the middle index of the array. Note that >> 1 is the same as divide by 2
    mid = start+((end-start)>>1);
    #Keep going left until we have reached the base case (left most index)
    t = findOneHelper(bString, start, mid);
    if(t != -1):
        #if an index is found, return that to indicate this is where the first "1"
        return t;
    #Check the right half
    return findOneHelper(bString, mid+1, end);

def findOne(bString):
    return findOneHelper(bString, 0, len(bString)-1);

The output for: 00001101000001010100000

>>> findOne("00001101000001010100000")
4

Test cases:
>>> findOne("000000000000000000000")
-1
>>> findOne("111111111111111111111")
0

At a high level the code should look like this, ofcourse you need to check the boundary case and overflows.

int FindIndexOfFirstOne(number, length)
{
	if (length < 1)
		return -1;
	int top = length-1;
	int bottom = 0;
	int curr = (top + bottom) /2;

	while (top > bottom)
	{
		if (number < 2^ (curr)) // all the bits on left of curr digits is 0
		{
			top = curr;
			curr = (top + bottom)/2;
		}
		else if (number == 2^(curr))
		{
			return curr;
		}
		else
		{
			if (number < 2^(curr+1)) //
				return curr;
			bottom = curr;
			curr = top + bottom / 2;
		}
	}
}

#include <iostream>
using namespace std;

int search(int *list, int start, int end)
{
	if(start > end) return -1;
	int middle = (start+end)/2;
	int nRet = -1;
	nRet = search(list, start, middle-1);
	if(nRet != -1) return nRet;
	if(list[middle] == 1) return middle;
	nRet = search(list, middle+1, end);
	if(nRet != -1) return nRet;
}

void main()
{
	int list[5]={1,0,1,0,0};
	int ret = search(list, 0, sizeof(list)/sizeof(int)-1);

	if(ret == -1) cout<<"Element Not Found"<<endl;
	else cout<<"Found at the location"<<ret<<endl;
}

findOne(int arr[], int start, int end)
 {
   if(start == end)
  	if(arr[start] == 1)
	 	return start
	return -1;

  t =   findOne(arr, start, mid);
    if(t != -1)
	return t;

 return findOne(arr, mid+1, end);
}

can somebody explain it for me ?

The above code looks to me is assuming the array is sorted, and it is the general case binary search, it will not work for this case.

int[] a = new int[10] { 0, 0, 0, 0, 0, 0, 1, 0, 0, 0 };
int i;
int length = a.Length-1;
for (i = 0; i < a.Length/2; i++)
{
if (a[i]==1)
{
break;
}
else
{
if (a[i]!=a[length])
{
i = length;
break;

}
}
length--;
}
Console.WriteLine(i);

public class Main {
    public static void main(Strings args[]) {
        int[] input = {0,0,0,1,0,0,0,01,1,1};
        OccurenceOf1.getOccurence(input, 0, input.length - 1);
    }
}

public class OccurenceOf1 {
    public static boolean getOccurence(int[] inputArray, int start, int end) {
       int middle = (start + end) /2; 
       if(inputArray == null  || inputArray.length == 0) {
            System.err.println("Empty Array");
            return false;
        }
        else if(middle == 0 && inputArray[middle] != 1) {
            return false;
        }
        else if(middle == input.length - 1 && inputArray[middle] != 1) {
             return false;
        }
        else if(inputArray[middle] == 1 && inputArray[middle - 1] !=  1) {
            System.out.println("First Occurence of 1 is " + middle);
            return true;
        }
        else if(getOccurence(inputArray, start, middle)) {
            return true;
        }
        else if(getOccurence(inputArray, middle, end)) {
              return true;
        }
        else return false;
    }
}

If bit vector represented as

int[] vector = { 0b0000000_00000000_00000000_00000000, 0b00001101_00000101_01000001_11001001, 0b00000000_00100101_01001001_10001111,  };

you can achieve O(n/31)

private int firstOneIndex( int[] vector ){

		final int BITS_PER_INT = 31;
		
		int offset = 0;
		
		for( int val : vector ){
			
			if( val > 0 ){
				int msbValue = Integer.highestOneBit(val);				
				return offset + (BITS_PER_INT - ((int)MathUtils.log2(msbValue) + 1)) + 1;
			}
			
			offset += BITS_PER_INT;
		}
		
		return -1;
	}

void bsearch(int item,int *a,int f,int l)
{

if(f<=l)
{
int k=(f+l)/2;


bsearch(item,a,f,k-1);
if(*(a+k)==item)
{
if(g==-1)
g=k;
}
bsearch(item,a,k+1,l);


}
}

We can apply binary search on this.
here is my example
if the given array is "000011010000"
First step, middle = (start + end)/2 = 6, then we compare "000001" with "000011" which is the first 6 digits from the given array.
"000011" is 3 in decimal and > "000001" = 1.
So, we need to search in the first part, which is start = 0, and end = middle = 6;
Second step, middle = 3, and we get "000" from array. "000" < "001". The target is shorten to digit 3 to 6
Third step, middle = 5, and we get "00001" is 1, we are done.

void binarySearch_arr(int a[],int start, int end,int* res)
{
	if(start >= end)
		return;

	if(a[start] == 1)
		*res =  start;
	int mid =  (start+end)/2;
	binarySearch_arr(a,start,mid,res);
	if(a[mid] == 1)
		*res = mid;
	binarySearch_arr(a,mid+1,end,res);
}

You guys are morons. How do you do binary search on an array which is not sorted?

C# solution

private static int FindFirst(int[] data, int startIdx, int endIdx)
        {
            if (data[startIdx] == 1)
                return startIdx;
            else if (startIdx == endIdx)
                return -1;
            else
            {
                int midIdx = Convert.ToInt32((startIdx + endIdx) / 2);
                //Search left
                int leftResult = FindFirst(data, startIdx, midIdx);
                if (leftResult == -1)
                {
                    //Look right
                    return FindFirst(data, midIdx + 1, endIdx);
                }
                return leftResult;
            }
        }

Assuming bitwise operators can be used, could this not be done easily using a slightly modified binary search? I'm short on time at the moment, so I'll just describe the algorithm.

Implement standard binary search, then modify the branch test as follows:

// bitwise "and" num with, e.g. 11110000. If > 0, must be a 1 on the left or current position
if ((~0 << (midpoint - 1)) & num > 0)
{
   // bitwise "and" num with, e.g. 11100000. If 0, the current midpoint must be the first 1
   if ((~0 << midpoint) & num == 0) //return midpoint
   else //branch left
}
else //branch right

Wrong question. Binary search is applicable only for the sorted array. Nothing better than linear search when array is not sorted.

We can tweak the merge sort to do binary search

#include<stdio.h>
#include<strings.h>
int bsearch(char a[],int low,int high)
{
int mid,index;
mid=low+(high-low)/2 ;
printf("%d%d\n",low,high) ;

if(low>high||low==high && a[low]=='0')
return -1 ;

index=bsearch(a,low,mid-1) ;
if(index!=-1)
return index ;

if(a[mid]=='1')
return mid ;

return bsearch(a,mid+1,high) ;
}

void main()
{
char s[100] ;
int i=0;
printf("enter the string\n") ;
gets(s) ;
fflush(stdin) ;
while(s[i++]!='\0') ;

printf("%d\n",i) ;
printf("at %d index first occurance of 1",bsearch(s,0,i-1)) ;
}

Do a left favored binary search for "1" and keep shrinking the window of search till you get you get the same index or you can't find any more ones

public static int First1Search(int[] array)
        {
            int left = 0;
            int right = array.Length - 1;
            int minIndex = -1;
            while (true)
            {
                int elementIndex = LeftFavoredSearch(array, left, right);
                if (elementIndex == -1 || elementIndex == minIndex)
                {
                    return minIndex;
                }
                else
                {
                    minIndex = elementIndex;
                    right = minIndex;
                }
            }
        }
        public static int LeftFavoredSearch(int[] array, int l, int r)
        {
            if (l > r)
            {
                return -1;
            }
            int mid = (l + r) / 2;
            if (array[mid] == 1)
            {
                return mid;
            }
            int leftSearch = LeftFavoredSearch(array, l,mid-1);
            if (leftSearch != -1)
            {
                return leftSearch;
            }
            else
            {
                return LeftFavoredSearch(array, mid+1, r);
            }
        }

Do a left favored binary search for "1" and keep shrinking the window of search till you can't find and more 1s or search index of 1 remains same

public static int First1Search(int[] array)
        {
            int left = 0;
            int right = array.Length - 1;
            int minIndex = -1;
            while (true)
            {
                int elementIndex = LeftFavoredSearch(array, left, right);
                if (elementIndex == -1 || elementIndex == minIndex)
                {
                    return minIndex;
                }
                else
                {
                    minIndex = elementIndex;
                    right = minIndex;
                }
            }
        }
        public static int LeftFavoredSearch(int[] array, int l, int r)
        {
            if (l > r)
            {
                return -1;
            }
            int mid = (l + r) / 2;
            if (array[mid] == 1)
            {
                return mid;
            }
            int leftSearch = LeftFavoredSearch(array, l,mid-1);
            if (leftSearch != -1)
            {
                return leftSearch;
            }
            else
            {
                return LeftFavoredSearch(array, mid+1, r);
            }
        }

since the numbers are 0s and 1s you can treat them as binary and stuff them into an int (so the first 32 elements form an integer, the next 32 another integer) and at the end you`ll have an array of ints. Now you can do a binary search agains 0. If the first element of the aray is greater than 0 then there's a one there. Split that byte into 16 bit integers and check the first half .. and so on until you find the one. Of course you need to track the displacement in the String.

1. You can't use binary search here, cause array isn't sorted.
2. If your data is represented as int[] arr = {0,0,0,0,1,1,0 ...}, you can't do better then O(n) time algorithm.

// AUTHOR: AMAN JAIN
#include <iostream>
#include <sstream>
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <deque>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <list>
#include <vector>
#include <queue>
#define sz(s) s.size()
using namespace std;
int search(string& s,int low,int high){
if(low>high)return -1;
int mid=low+(high-low)/2;
int po=search(s,low,mid-1);
if(po!=-1)return po;
if(s[mid]=='1')return mid;
po=search(s,mid+1,high);
if(po!=-1)return po;
return -1;
}

int main(){
string s;
cin>>s;
int po=search(s,0,sz(s)-1);
if(po!=-1)cout<<po<<"\n";
else printf("1 is not in string\n");
	return 0;
}