CareerCup

Yes binary search, but we continue moving left even if we find a match.

int leftmost(int [] a, int x) {
    int L = 0;
    int R = a.Length-1;
  
    if (R < 0) return -1; //empty array
   
    while (R - L > 1) {
        int mid = (R-L)/2 + L;
        if (a[mid] < x) {
            L = mid;
        } else {
            R = mid;
        }
    }
    
    if (a[L] == x) {
        return L;
    }
   
    if (a[R] == x) {
        return R;
    }
    
    return -1;
}

public class FirstOccurence {
private static int getFirstIndexOf(Integer[] sorted,int lindex,int rindex,int n){
	if (rindex==lindex){
		return -1;
	}
	int mindex = (lindex+(rindex-lindex)/2);
	if (sorted[mindex]==n){
		int curr= mindex;
		int first = getFirstIndexOf(sorted, lindex, mindex, n);
		if (first!=-1) curr=first;
		return curr;
	}
	else if (sorted[mindex]<n){
		return getFirstIndexOf(sorted, mindex+1, rindex, n);
	}
	else{
		return getFirstIndexOf(sorted, lindex, mindex, n);
	}
}
public static void main(String[] args) {
	Integer[] sorted={2,3,3,3,3,3,3,4};
	System.out.println(getFirstIndexOf(sorted, 0,sorted.length,3));
	System.out.println(getFirstIndexOf(sorted, 0,sorted.length,4));
	System.out.println(getFirstIndexOf(sorted, 0,sorted.length,5));
}
}

This comment has been deleted.

binary search

if found , check element to its left if still the same number do binary search on left.
until number to its left is not the number we have to find.
the moving left solution is not optimal,
as suppose we have 100 3's in an array we have to move to the left several times which is not optimal.

do reverse binary search from left...

The solution to this problem is very simple. Just use a TreeMap as your primary datastructure. TreeMap is guaranteed polynomial runtime. Very fast. O(n) guaranteed!

Create a binary tree and find the element with a pre-order traversal.

Sorry about the solution why would be do an O(n) pass over the array when we have the solution in O(lg n) binary search over the array.

#include<iostream>
#include<vector>
using namespace std;
vector<int> v;
void b_search(int,int,int);
int main()
{
v.push_back(1);
v.push_back(2);
v.push_back(2);
v.push_back(2);
v.push_back(3);
v.push_back(4);
cout<<"enter the value to be found:\n";
int k;
cin>>k;
int l=0,r=v.size()-1;
b_search(l,r,k);
system("pause");
return 0;
}
void b_search(int l,int r,int k)
{
//cout<<"cvhdsavb\n";
if(l>r)return ;
int m=(l+r)/2;
if(v[m]==k && m==0){cout<<"value found at "<<m; return ;}
else if(v[m]==k && v[m]>v[m-1]) {cout<<"value found at "<<m; return ;}
else if(v[m]>=k){cout<<"else_it\n"; b_search(l,m,k);}
else {cout<<"else\n";b_search(m+1,r,k);}
}

i don't understand this question... what do you mean by first occarance

I would not use Binary search. The problem is the sorted array is not a completed binary search tree.

Since the array is sorted. So the size of array is known. I will first compare the number in the middle with the searched number, then do the recursive search on the half array based on the comparison result, until we find the first occurrence.

int searchNumberinArray(int numberSearched, int array[], int leftIndex, int rightIndex)
{
int size = rightIndex - leftIndex + 1;
int middleIndex = ( leftIndex + rightIndex ) / 2;

if ( array[middleIndex] < numberSearched ) {
searchNumberinArray(numberSearched, array, leftIndex, middleIndex - 1);
} elseif array[middleIndex] > numberSearched {
searchNumberinArray (numberSearched, array, middleIndex + 1, rightIndex );
} else {
// the first occurrence is in the first half
for (int i = leftIndex; i < middleIndex; i++)
{
if (array[i] == numberSearched)
return i;
else
return middleIndex
}
}

return -1; // nothing found

}

/**
     * Find the first occurance of a number in a sorted array.
     * 
     * @param arr The array to be searched.
     * @param target
     * @return The index of the first occurance, return -1 if not found.
     */
    public int searchFirstOccurance(int[] arr, int target) {
        
        int lo = 0;
        int hi = arr.length;
        
        while(lo < hi) {
            int mid = lo + (hi - lo)/2;
            if(arr[mid] < target) {
                lo = mid + 1;
            } else if(arr[mid] > target) {
                hi = mid - 1;
            } else {//arr[mid] == target
                hi = mid;
            }
        }
        
        if(arr[lo] == target)
            return lo;
        else return -1;
    }

I present two solutions to the above problem.
Appr 1:- We can essentially scan through the entire array and perform a linear search. But this would take O(n) time complexity and O(1) SC.

Appr 2:- Since the number is sorted, we can do a modified binary search and reduce search space at every step. This would take O(logn) and O(1) SC.

I present both solutions in Python below:

def findFirstOccLinear(nums, target):
  for ind, num in enumerate(nums):
    if num == target:
      return ind
  return -1

def findFirstOccurenceBS(nums, target):
  index = -1
  l, r = 0, len(nums) - 1
  while l <= r:
    mid = (l + r) // 2
    if nums[mid] == target:
      index = mid
      r = mid - 1
    elif nums[mid] > target:
      r = mid - 1
    else:
      l = mid + 1
   return index