CareerCup

int modifiedBinarySearch(int arr[], int left, int right)
{

while(left <=  right and (right - left >= 0) )
{
          int mid = (right + left)/2;
          if (arr[mid] == 0)
                     left = mid + 1;
          else 
               //Check if the element left to 1 is 0, then mid is the starting position
               if (mid > 0 && arr[mid - 1] == 0) 
                     return mid;
               // Binary search towards the left
               else if (mid > 0 && arr[mid - 1] == 1)
                     right = mid - 1;    
}
// Return - 1 when the arr has all zeros or no elements
return -1;
}

int main()
{
int arr[5] = {0, 0, 0, 1, 1};
cout<<modifiedBinarySearch(arr, 0, 4);
return 0;
}

Apply binary search with extra concern that check the right and left element.

int Bin(int a[],int i,int j)
{
if(i>j )
return -1;

mid=i+ (j-i)/2;

if(mid==0 && a[mid]==1)
return 0; //first element
if(mid>0)
if(a[mid]==1 && a[mid-1]==0 )
return mid;

if(a[mid]==0)
return bin(a,mid+1,j);
if(a[mid]==1)
return bin(a,i,mid-1);
}

int a[10] = {0,0,0,1,1,1,1,1,1,1};
for(int i=0; i<a.length;i=i+2){

if (a[i] + a[i+1] = =1)
{s.o.p("Count = "+(i+1));
break;
}


if(a[i]+a[i+1]==2)
{s.o.p("Count = "+(i));
break;
}

}// for loop end

Use Binary search to find index for first occurrence and last occurrence of 1's .. so no. of occurences = last_index - first_index + 1

add the elements starting from index 0 until you get a value 1, that index would be the answer.

worst case =O(n)
int s=0;
for(int i=0; <n; i++)
{
s+= a[i];
if(s)
{
printf("found first one at an Index %d", i);
break;
}
}

O(n) solution
int a[10]={0,0,0,0,0,1,1};
for(int i=0;i<10;i++)
{
if(a[i]>0)
return i;
}

using binary search strategy :

int first1(int * a , int low , int high ) {

if ( low > high )
return -1;
else if( low == high ) {
if(a[low] == 1)
return low;
else return -1;
}
else {
int mid = (low +high )/2;
if( a[mid] == a[mid+1] ){
if(a[mid] == 1)
return first1(a,low,mid);
else
return first1(a,mid+2,high);
}

else return (mid+1) ;
}

}
}

using binary search strategy :

int first1(int * a , int low , int high ) {

if ( low > high )
return -1;
else if( low == high ) {
if(a[low] == 1)
return low;
else return -1;
}
else {
int mid = (low +high )/2;
if( a[mid] == a[mid+1] ){
if(a[mid] == 1)
return first1(a,low,mid);
else
return first1(a,mid+2,high);
}

else return (mid+1) ;
}

}
}

using binary search strategy :

int first1(int * a , int low , int high ) {

if ( low > high )
return -1;
else if( low == high ) {
if(a[low] == 1)
return low;
else return -1;
}
else {
int mid = (low +high )/2;
if( a[mid] == a[mid+1] ){
if(a[mid] == 1)
return first1(a,low,mid);
else
return first1(a,mid+2,high);
}

else return (mid+1) ;
}

}
}

binary search:

int findOne(vector<int> a)
{
	int start = 0;
	int end = a.size() - 1;
	int middle;

	while(start >= 0 && start <= end)
	{
		middle = (start + end) / 2;
		if(a.at(middle) == 1)
		{
			if(middle == 0 || a.at(middle - 1) == 0)
				return middle;
			else
			{
				end = middle - 1;
				continue;
			}
		}
		else
			start = middle + 1;
	}
	return -1;
}

My question is: Why will someone want to ask this ? What is the use ?

My question is: Why will someone want to ask this ? What is the use ?

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

int main()
{
   int ip[] = {0,0,0,0,0};
   printf("The op indx is :%d",find(ip,0,4));
   return 0;
}

using binary search technique, time complexity is O(log n)
int low=0,hi=n-1;
while(low<=hi)
{
int mid=(low+hi)/2;

if(A[mid-1]==1)
hi=mid-1;
else if(A[mid]==1)
return mid+1;
else if(A[mid+1]==1)
low=mid+1;
else
low=mid+1;
}
return 0;

any change pls reply

using binary search strategy and with out recursive function:

int low=0,hi=n-1;
     while(low<=hi)
     {
          int mid=(low+hi)/2;
          
          if(A[mid-1]==1)
              hi=mid-1;
          else if(A[mid]==1)
              return mid+1;
          else if(A[mid+1]==1)
              low=mid+1;
          else
              low=mid+1;
              }
     return 0;
can any one tell me the time complixity for this algo

using linear search strategy:
for(i=0;i<n;i++)
        if(A[i]!=0)
            return i+1;
    return 0;

to opimize the solution.
we dont need to compare the no.
just do addition and subtraction.

sum=0;
for(i=0;i<n;i++)
sum=sum+a[i];
index=n-sum;
return index+1;

i have a doubt , which is more expensive comparison or addition ?

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

void modifiedBinarySearch(int arr[], int left, int right, int &pos)
{

if (left<right)
{
int mid = (right + left)/2 +1;
if (arr[mid] == 0)
{
modifiedBinarySearch(arr, left, mid-1, pos);
modifiedBinarySearch(arr, mid+1, right, pos);
}
else
{
pos = (pos > mid) ? mid : pos;
modifiedBinarySearch(arr, left, mid-1, pos);
}
}
else
return;
}



int main()
{
int arr[6] = {0, 1, 1, 0, 1, 1};
int position=6;
modifiedBinarySearch(arr, 0, 5, position);
cout<<position<<endl;
return 0;
}