CareerCup

Since the array is 'unlimited' in size we need to find a valid 'end' before we start searching.

1. Find an end (check 2^1,2^1,2^2,2^3...) if it's bigger than the number searched or you get an exception that's your end.
2. Do a binary search range 2^(i-1) - 2^i for your number when you find the value save the index but keep searching via binary search. Cover examples like [1,2,(100,000 2's), 3,4,5,..................]
3. When your finished with all binary searches in the found range the last seen index is the largest location of that number.

Pseudo Code:

for i = 1 to MAX_SIZE do{
         if(A[pow(2, i)] <= num) continue;
         else break;
}
//the last occurrence lies between 2^(i-1) & 2^(i) 
//Now this can be found by binary search.
Time Complexity - O(logn)

1. Binary search - to find the number
2. To find the last index of the number, traverse till the next number changes
3. Return the index

Algorithm:
* Initialize lo to 0, hi to 1.
* Do hi = hi * 2 while data[hi] <= x
* Then do binary search between lo and hi for the first element greater than x

The best tutorial on binary search I ever read is on TopCoder (search in google with "topcoder" and "binary search" keywords - can't do links here)

int findLastOccurrence(int[] arr, int num){
   int i = 0;
   int index = 0;
   while(arr[index] <= num) {
     index = 1 << i;
     ++i;
   }
   
   int left = index/2 ;
   int right = index;
   
   while(left < right){
     int mid = (left + right)/2;
     if(arr[mid] == num){
       
        if( (arr[mid + 1] )!=num){
          return mid;
        }else{
          
          left = mid + 1;
        }
     }else if(arr[mid] < num){
         left = mid + 1;
     }else{
     
         right = mid - 1;
     } 
   
   }

int function(int a[],int size,int key)
{
int mid,first=0,last = size-1,index;
mid = (first+last)/2;
while(first < last)
{
if(a[mid] == key)
{
while(mid < last)
{
if(a[mid] == key)
{
index = mid;
mid++;
}
else
return index;
}
}
else if(a[mid] < key)
first = mid+1;
else
last = mid-1;
mid = (first+last)/2;
}
return 0;

}

plz read. We do not know the size of the array.

Apply binary search repeatedly until the match is not found.

int find_last_occurance(int key, int *p , int length)
{
	int start_index = -1;	
	int last_index = -1; 
	int end_index = length -1;	
	while(1){
	    printf(">>>> starting the search in array [%d .. %d] <<< \n",start_index+1,end_index);
		start_index = search(key,p,start_index+1 , end_index);
		if(start_index == -1){		     
			return last_index;
		} else {
			last_index = start_index;
		}		
	}	
}

Everyone here has answered assuming its finite series and you know the length.

Since questions says it's infinite series , binary search is not a possibility. If it is infinite series and sorted then O(n) is the best solution I can think of. But even brute force answer leads to O(n) only.

public class indexvaluereturn
{
static int[] b = new int[15];
static public int count;
public int i,j,k;
public int indexreturn(int x){
int[] a = {1,2,2,3,3,3,4,6,6,6,6,6,8};
int length = a.length;
for(j=0;j<length;j++){
if(a[j]==x)
k = j;
}
System.out.println(k);
return 0;
}
public static void main(String argp[]){

indexvaluereturn k = new indexvaluereturn();
k.indexreturn(3);


}

}

I guess by infinite he means its a stream. And at any given time we need to find the last known occurrence of given number.

So we can maintain a HashMap of the number and its last occurrence

#include <iostream>

using namespace std;

int getLastIndex(char *inputNumbers,int number)
{
    int sortedArray[9]={0};
    char strNumber[2];
    int count = 0;
    while(*inputNumbers)
    {
        memset(strNumber,'\0',2);
        strncpy(strNumber,(const char *)inputNumbers,(size_t)1);
        int value = atoi(strNumber);
        sortedArray[value]=count;
        inputNumbers++;
        count++;
    }

    return sortedArray[number];
}

int main(int argc, char *argv[])
{
    char inputNumbers[256]={0};
    int number = 0;
    cout<<"Enter the Sequence of Number in sorted manner (E.g. 1223344556666) : ";
    cin>>inputNumbers;
    cout<<"Enter the number to check the index from above sequence : ";
    cin>>number;

    int indexLocation = getLastIndex(inputNumbers,number);
    cout<<"The last index location : "<<indexLocation<<endl;
    exit(0);
}

A very dirty implementation written in C, but keeps the O(logn) efficiency.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/*
There is a sorted array of infinite numbers (can contain duplicates). 
Given a number. Find the last occurring instance of that number 
in the array.
*/
int find_last(int* a, int size, int num)
{
	
	int pos = 0;
	int power = 1;
	while(pos <= size)
	{
		// check if we found the number
		if (a[pos] == num)
			break;

		// check if we passed the number
		if (a[pos] > num)
		{
			pos = pow(2, power-1);
			break;
		}

		// if we're not there yet, make a step
		power++;
		pos = pow(2, power);
	}

	// now, where did we leave off...

	// if we didn't find the number yet, 
	// do a little binary search
	if (a[pos] != num || pos > size)
	{
		int l, r;
		if (pos > size)
		{
			l = pow(2, power-1);
			r = size;
		}
		else
		{
			l = pos;
			r = pow(2, power);
			if (r > size)
				r = size;
		}

		int mid = l + (r - l)/2;

		// lets loop until we find the number
		while (1)
		{
			mid = l + (r - l)/2;

			// take care of corner cases
			if (a[l] == num)
			{
				pos = l;
				break;
			}
			else if (a[r] == num)
			{
				pos = r;
				break;
			}
			else if (a[mid] == num)
			{
				pos = mid;
				break;
			}

			// too far?
			if (num > a[mid])
				l = mid;
			// not far enough?
			else if (num < a[mid])
				r = mid;

			// i guess we didn't find what we came for...
			if (l+1 == r && a[l] != num && a[r] != num)
				return -1;
		}

	}

	// by now we should have found our number, 
	// lets find the last occurence
	while (a[pos+1] == num && pos <= size)
		pos++;

	return pos;

}

int main()
{
	int array[] = {0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 8};
	int size = (int)(sizeof(array)/sizeof(int));

	int location = find_last(array, size-1, 4);
	printf("location: %d\n", location);
}

We can convert simply the integer array to String Object and use lastindexof() to find the required position.

assume we have infinite memory
Pseudo Code:
1)find the upper bound, O(log n)
i=1
while( A[pow(2,i++)] <=num );
2) bin search( A, pow(2,i-1), pow(2,i) ), O(log n)

(index of given number +1) is the answer. :)

After reading all the comments, I feel the answer is not perfect!

Point to be noted here is that the input is unlimited. There is no end to it, say you are reading a stream of data from some source. So finding the end (whether actual end or where the number becomes greater than what we were searching for), is not possible. Hence, we cannot apply binary search directly!
I suggest the following solution:

1. Take i=0
2. If 2^i <= key && 2^(i+1) > key, then we have found the range, else increment i.
3. Once the range is found (say indexes r1 and r2), there are two conditions that are possible
a. value at r1 == key, or
b. value at r1 is less than key.

if condition a then,
we can do a binary search* to find the last index of the key.

if condition b then,
we can do a binary search to find some index of key (to make it like condition a)
and then do a binary search* to find the last index.

Note: binary search* => a modified version of binary search where we find the index of input change, to find the last index.

I think this will cover the all the cases of input and give a O(log n) solution. If I am missing anything or have made a mistake, please leave a comment.

1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);
/* if x is present in arr[] then returns the count of occurrences of x,
otherwise returns -1. */
int count(int arr[], int x, int n)
{
int i; // index of first occurrence of x in arr[0..n-1]
int j; // index of last occurrence of x in arr[0..n-1]

/* get the index of first occurrence of x */
i = first(arr, 0, n-1, x, n);

/* If x doesn't exist in arr[] then return -1 */
if(i == -1)
return i;

/* Else get the index of last occurrence of x. Note that we
are only looking in the subarray after first occurrence */
j = last(arr, i, n-1, x, n);

/* return count */
return j-i+1;
}

/* if x is present in arr[] then returns the index of FIRST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}


/* if x is present in arr[] then returns the index of LAST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int last(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
return mid;
else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}

/* driver program to test above functions */
int main()
{
int arr[] = {1, 2, 2, 3, 3, 3, 3};
int x = 3; // Element to be counted in arr[]
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
printf(" %d occurs %d times ", x, c);
getchar();
return 0;
}

Scala:

def lastRecurringInstance(xs: Array[Int], i: Int, currIdx: Int, idx: Int): Int = xs match {
 case Array() => idx
 case Array(x, y@_*) if(x > i) => idx
 case Array(x, y@_*) if(x == i) => lastRecurringInstance(y.toArray, i, currIdx+1, currIdx)
 case Array(x, y@_*) if(x < i) => lastRecurringInstance(y.toArray, i, currIdx+1, idx)   
}

scala> val xs = Array(1,2,3,4,4,4,4,5,5,6,6,6,6,7,7,8,9)
xs: Array[Int] = Array(1, 2, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, 8, 9)

scala> val r = lastRecurringInstance(xs, 6, 0, -1)
r: Int = 12

scala> val r = lastRecurringInstance(xs, 7, 0, -1)
r: Int = 14