CareerCup

logn
perform binary search

Binary Search to find an instance of the given number, then scan backward to find the first instance of the given number, as the array is sorted.
Time complexity is O(n).

Perform binary search.

int findFirstOccurrence(int* arr,int l,int h,int tofind)
{
        int mid;
        if(l>h) return INT_MIN;
        if(l==h)
                return arr[l]==tofind?l:-1;
        mid=(l+h)>>1;
        
        if(arr[mid]==tofind && (mid==l || arr[mid]>arr[mid-1]))
                return mid;
        if(tofind<=arr[mid])
                return findFirstOccurrence(arr,l,mid-1,tofind);
        return findFirstOccurrence(arr,mid+1,h,tofind);
}

Complete code here: ideone.com/8q91s

public class BinarySearch {

    //both from and to are inclusive.
    static int minOccurance(int[] array, int from, int to, int v) {
        if(from == to) {
            if(v == array[from]) {
                return from;
            } else {
                return -1;
            }
        }

        int middle = (from + to) >> 1;
        if(v < array[middle]) {
            return minOccurance(array, from, middle-1, v);
        } else if (v > array[middle]) {
            return minOccurance(array, middle + 1, to, v);
        } else {
            int left = minOccurance(array, from, middle-1, v);
            if(left == -1 ) {
                return middle;
            } else {
                return left;
            }
        }
    }


    public static void main(String[] args) {
        int[] arr = new int[] {1,1,1,1,1,1,1,1,1, 2, 2,2, 4,4,5,5,5,5,5,5,5};

        System.out.println(minOccurance(arr, 0, arr.length - 1, 1));
        System.out.println(minOccurance(arr, 0, arr.length - 1, 2));
        System.out.println(minOccurance(arr, 0, arr.length - 1, 3));
        System.out.println(minOccurance(arr, 0, arr.length - 1, 4));
        System.out.println(minOccurance(arr, 0, arr.length - 1, 5));
    }
}

//using binary search
int findIndex(int *arr, int low, int high, int data)
{
	int mid = (low+high)/2;

	if(arr[low] == data)
		return low;
	else if(arr[mid] >= data)
		return findIndex(arr, low , mid, data);
	else
		return findIndex(arr, mid+1, high, data);
}
//assumed that number is present in array

public static int findFirstNum(int[] input,int start,int end,int target)
	{
		if(start>end)
			return -1;
		else
		{
			int middle=(start+end)/2;
			if(target<=input[middle])
			{
				int index=findFirstNum(input,start,middle-1,target);
				if(index==-1)
				{
					if(input[middle]==target)
					{
						return middle;
					}
					else
						return -1;
				}
				else
					return index;
				
			}
			else
			{
				return findFirstNum(input,middle+1,end,target);
			}
		}
	}

public class Find_First_Instance_In_Sorted_Array {

public static int find_first(int[] test,int aim){
int result_index=find(test,aim,0,test.length-1);
return result_index;
}
public static int find(int[] test,int aim,int begin,int end){
if(begin==end){
if(test[begin]==aim){
return begin;
}
else{
return -1;
}
}
if(begin==end-1){
if((test[begin]==aim)||(test[end]==aim)){
if(test[begin]==aim){
return begin;
}
if(test[end]==aim){
return end;
}
}
else{
return -1;
}
}

int mid=(begin+end)/2;
if(test[mid]>aim){
return find(test,aim,begin,mid-1);
}
if(test[mid]<aim){
return find(test,aim,mid+1,end);
}
if(test[mid]==aim){
return find(test,aim,begin,mid-1)!=-1?find(test,aim,begin,mid-1):mid;
}

return -1;
}
public static void main(String[] args) {
int[] test=new int[]{1,2,3,3,3,3,4,5,6,7,7,8};
int aim=3;
int result_index=find_first(test,aim);
System.out.println(result_index);

}

}

The complexity can be 2*logn first to find the number then next binary search to find the first instance

In worse case you have to make (n/2) comparision.so the time complexity is o(n)

1. find the index of a number just less then the required number by bin search.
2. find the index of the given number.
3.now max &min limit we got we can find the 1st occurrence in O(logn) time now...

Time Complexity: O(log n)

int First_Instance(int A[], int min, int max, int k){
int mid = (min+ max)/2;
int index, temp;

if(min<=max){
if(k< A[mid])
index= First_Instance(A, min, mid- 1, k);
else if(k> A[mid])
index= First_Instance(A, min, mid- 1, k);
else
while(A[mid]!= k){
temp= mid;
mid++;
}
return temp;
}
return -1;
}

i1 = 0, i2= arr_end
Loop till (mod(i1 - i2) != 1)
1. Binary search from i1 to i2, ill the number is found: - store the index - i2
2. Continue the binary search on the left, till the next lower number is found- if no number is lower, return 0.
else store index - i1

return i2;

P.S : Not a very clear algo but hope its explanatory.

Complexity will be log(n)

I'm not sure if I'm missing anything or misunderstood the question. If you just do a Binary Search, this will only find the "target", i.e., the value it's looking for, but it is not guarantee the first occurance. As someone mentioned up there that we still have to do a backward scan to make sure that is the first occurance, why can't we just do a forward scan at the first place and return the first one it sees. This way we don't have to do a Binary Search and the run time will be O(n), which is equals to O(logn)+O(n).
Please let me know if I'm wrong, maybe I misread this problem.

-> Perform Binary Search
-> Continue binary search until we get first occurrence.

Important point : If data is sorted in increasing order then we need to move the index towards left direction. However Middle index could be also termination point.

Order : Log(n)

if it is sorted, then next element is same or previous element is same ... you simply increment its index or decrement to find. first decrement and then increment.

Here is the code with complexity log(n)

#include <stdio.h>

/*
 * Find the first occurence of the given number in index.
 */
void main()
{
    int nums[] = {1,1,3,5,8,8,8,10,12,23,23,55};
    int len = sizeof(nums)/sizeof(int);
    int start = 0, end = len-1, search = 8;
    int found_right = -1;
    while ((end - start) > 1)
    {
        if (found_right != -1)
        {
            if (nums[end] != search)
            {
                break;
            }
            found_right = end;
            end -= 1;
            continue;
        }
        int mid = (end + start)/2;
        int val = nums[mid];
        if (val == search)
        {
            end = mid-1;
            found_right = mid;
        }
        else if(val < search)
        {
            start = mid;
        }
        else
        {
            end = mid;
        }
    }
    if (found_right != -1)
    {
        printf("found at %d", found_right);
    }
    else
    {
        printf("Sorry!");
    }
}

Implement binary search to find the required number ,then compare it with the number on the left ,if it is different this position is your answer or else binary search on the remaining part ,,so it cannot be more than O(logn)