CareerCup

int binarySearch(int arr[], int start, int end, int key)
{
	if(end < start) return -1;
	int mid = start + (end - start) / 2;
	if(arr[mid] == key)
	{
		int leftIndex = binarySearch(arr, start, mid - 1, key);
		return (leftIndex == -1 ? mid : leftIndex);
	}
	else if(arr[mid] > key)
	{
		return binarySearch(arr, start, mid - 1, key);
	}
	else
	{
		return binarySearch(arr, mid + 1, end, key);
	}
}

Perform a binary search to find that member exists in the list or not.
1. If not found then return -1. Complexity will be log (n)
2. If found then start looking backward in the list till you hit lower variable then the current item, and then return the index of currentItem. Worst case complexity will be log(n) + n

int binSearch(int arr[], int low, int high, int element)
{
	if(low > high)
		return -1;
	int mid = (low + high) / 2;
	if(arr[mid] == element) //found one occurrence
	{
		//we have to find if any other occurrence is there with less index
		if(binSearch(arr, low, mid-1, element) == -1) //no occurrence with less index is found
			return mid; // return the only occurrence
		else
			binSearch(arr, low, mid-1, element);
	}
	else if(arr[mid] > element) //element is lesser than arr[mid]
		binSearch(arr, low, mid-1, element); //search in the lesser half
	else if(arr[mid] < element) //element is greater than arr[mid]
		binSearch(arr, mid+1, high, element); //search in greater half
	else
		return -1; //not found at all
}

public class FirstOccurrance {
    public int findFirst(int[] a, int target)
    {
        int first = 0;
        int last = a.length - 1;
        while (first <= last)
        {
            int mid = (first + last) / 2;
            if (a[mid] == target)
            {
                if (mid + 1 == a.length || first == last)
                {
                    return mid;
                }
                else
                {
                    last = mid;
                }
            }
            else if (a[mid] < target)
            {
                first = mid + 1;
            }
            else
            {
                last = mid - 1;
            }
        }
        return -1;
    }
}

int find(int arr[], int f, int l, int num)
{
int m = (f+l)/2;

if(f<=l)
{
if(arr[m]==num && arr[m-1]<num)
return m;

else if(num < arr[m] || num == arr[m])
find(arr,f,m-1,num);

else if(num > arr[m])
find(arr,m+1,l,num);

}
else
return -1;
}

for (int i = 0; i < array.Length ; i++)
{
if (search_item ==array[i])
{
result_index = i ;
break;
}
if ((i==array.Length-1) && (search_item!=array[i]))
{
result_index = -1;
}
}

int search(int a[], int low, int high, int num)
{
	if(low>high)
	 return -1;

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

#include<stdio.h>
int main()
{
int a[]={2,2,2,3,4,5,5,6,6,8,9},i,index=-1,num;
printf("enter the number to bve searched:  ");
scanf("%d",&num);
for(i=0;i<(sizeof(a)/sizeof(a[0]));i++)
{
if(num==a[i])
{
printf("no is at position : %d\n",i);
index++;
break;
}
}
if(index==-1)
{
printf("%d",index);
}
return 0;
}

1. Find the occurrence of an element using standard binary search
2. If found change the end index to the index of the found element and apply binary search again. Do this until the beginning pointer meets the end.

Complexity should be log(n)

Here is a code

public static int binSearch(int[] a, int beg, int end, int item) {

        int mid;
        while (beg <= end) {
            mid = (beg + end) / 2;
            if (a[mid] == item) {
                if (beg == end) {
                    return mid;
                } else {
                    return binSearch(a, beg, mid, item);
                }
            } else if (item < a[mid]) {
                end = mid - 1;
            } else {
                beg = mid + 1;
            }
        }

        return -1;

    }

sites.google.com/site/spaceofjameschen/home/sort-and-search/find-first-element-in-an-array

//performs a binary search on a sorted array of comparable elements
	//returns index of target element if found or -1 otherwise
	public int findFirstOccurrence (int [] values, int target){

		//beg is the beginning index of the sub-array we are looking at
		int beg = 0;
		//high is the end index of the sub-array we're looking at
		int end = values.length - 1;
		//mid is the middle element of the sub-array we're looking at
		int mid = (beg + end)/2;

		while (beg <= end) {
			//we proceed to compare target to mid
			if (values[mid] < target) {
				beg = mid + 1;
				mid = (beg + end)/2;
			} else if (values[mid] > target) {
				end = mid - 1;
				mid = (beg + end)/2;
			} else {
				//value at mid == target
				//go backwards and find first occurrence of target
				int targetIdx = mid;
				while (targetIdx - 1 >= 0 && target == values[targetIdx - 1]){
					--targetIdx;
				}
				return targetIdx;
			}
		}
		//beg = end and target was not found. Hence, target was not in array
		return -1;
		//time complexity O(logn)
	}

Test

My solution is a binary search. I believe the complexity of this solution is O(logn)

#include <stdio.h>
#include <vector>

using namespace std;
int first_least(vector<int> &v, int key) {
  int begin,end, m;
  
  begin = 0; end = v.size();
  int f_id = -1;
  while (begin <= end) {
    m = (begin + end) / 2;
    if (v[m] > key)
      end = m - 1;
    else if (v[m] < key)
      begin = m + 1;
    else {
      f_id = m;
      end = m - 1;
    }
  }
  
  return f_id;
}

int bsearch(int a[], int length, int key)
    {
        int left, right, mid;
        
        left = -1;
        right = length;

        while (left + 1 != right)
        {
            mid = (left + right) / 2;
            if (a[mid] < key)
            {
                left = mid;
            }
            else
            {
                right = mid;
            }
        }

        if (right < length && a[right] == key)
            return right;

        return -1;
    }

int binarySearch(int a[], int x) {
	int s = 0, e = a.length - 1, m;
	while (s < e) {
		m = (s + e) >> 1;
		if (a[m] == x) {
			e = m;
		} else if (a[m] < x) {
			s = m + 1;
		} else {
			e = m - 1;
		}
	}
	return (s == e && a[s] == x) ? s : -1;
}

public int calculatePosition(int num){

int ret=-1;

int a[]={2,2,2,3,4,5,5,6,6,6,7};


for (int i = 0; i < a.length; i++) {

if(a[i]==num){

ret=i;

break;

}

}

return ret;
}

A simple Binary search with time complexity: O(logn)

public static int getFirstOccuranceOfGivenNumber(int[] A, int p, int r, int k)
{
if (p > r)
{
return -1;
}

if (p == r && A[p] == k)
{
return p+1;
}

if (p+1 == r)
{
if (A[p] != k && A[r] != k)
return -1;
else if (A[p] == k && A[r] == k)
{
return p+1;
}
else
{
if (A[p] == k)
return p+1;
else
return r+1;
}
}

int mid = (p+r)/2;
if (A[mid] == k && A[mid-1] != k)
{
return mid+1;
}
else if (A[mid] < k)
{
return getFirstOccuranceOfGivenNumber(A, mid+1, r, k);
}
else
{
return getFirstOccuranceOfGivenNumber(A, p, mid-1, k);
}
}

int getFirstOccurance(int[] sortedArr,int first,int last,int s)
{
   if(first > last) return -1;
   int mid = (first + last )/ 2;
   if(sortedArr[mid] == s && (sortedArr[mid-1] != s || mid -1 == 0) )
        return mid;
   if(sortedArr[mid] >= e)
        return getFirstOccurance(sortedArr,mid+1,last,s);
   return getFirstOccurance(sortedArr,fist,mid-1,s);
}

In most of the functions you are passing first and last element but how your program gets last element from array??

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

	int mid=(start+end-1)/2;
	if(arr[mid]==val)
		return mid;

	if(arr[mid]<val)
		searchInSorted(arr,val,mid+1,end);
	else
		searchInSorted(arr,val,start,mid);
}
int searchInSorted(int arr[],int val,int size)
{
	int pos = searchInSorted(arr,val,0,size);
	int tmp=pos;
	while(arr[tmp]==val&&tmp>=0)
		tmp--;
	return tmp+1;
}

public long SearchFirstOccurence(int[] values, int lookupValue)
{
	if (values = null || values.Count == 0)
		return -1;

	long start = 0;
	long end = values.Count - 1;
	
	while (start <= end)
	{
		mid = (end-start)/2 + start;


		if (values[mid] == lookupValue)
		{
			foundIndex = mid;
			break;
		}

		if (values[mid] > lookupValue)
		{
			end = mid - 1;
		}
		else
		{
			start = mid + 1;
		}
	}

	if (foundIndex > 0)
	{
		start = 0;
		end = foundIndex;

		while (start <= end)
		{
			if (start == end)
			{
				return start;
			}

			mid = (end-start)/2 + start;

			if (values[mid] == lookupValue)
			{
				end = mid - 1;
			} 
			else
			{
				start = mid + 1;
			}
		}
	}
	
	return -1;
}

Binary Search to find number. If the number is found, continue searching left see if there is an earlier occurence of the number. The binary search will always return where there are no more numbers to search. It will not return when an initial match is found.

Runtime is O(log n),actually Theta(log n) because upper and lower bound is log n.

public static int findFirstOccurance(int numArray[], int searchNum)
    {
       int firstOccuranceIndex = -1;
       int min_index = 0;
       int max_index = numArray.length- 1;
       int currentIndex;
    
       while(min_index <= max_index) {
          currentIndex = (max_index + min_index)/2;
          if( numArray[currentIndex] == searchNum ) {
              firstOccuranceIndex = currentIndex;
              max_index = currentIndex - 1;
          } else if( numArray[currentIndex] > searchNum ) {
              max_index = currentIndex - 1;          
          } else {
              min_index = currentIndex + 1;
          }
    
       }
    
       return firstOccuranceIndex;
    
    }

The main idea is to find occurrence using binary search, and then go left as far as possible, increasing step each time. When step cannot be increased anymore, go left reducing step. Time complexity is O(ln(n))
Sample code in C#:

static int BinSearch<T>(T[] arr, T value) where T : IComparable<T>
{
    int lower = arr.GetLowerBound(0), upper = arr.GetUpperBound(0);
    while (lower <= upper)
    {
        int center = (lower + upper) / 2;
        if (value.CompareTo(arr[center]) > 0) lower = center + 1;
        else
            if (value.CompareTo(arr[center]) < 0) upper = center - 1;
            else
            {
                // occurrence found, go left as far as possible
                int step = 1;
                for (; ; step *= 2)
                {
                    if (center - step >= lower && 
                        arr[center - step].CompareTo(value) == 0) center -= step; 
                    else 
                        break;
                }
                for (; step > 0; step /= 2)
                {
                    if (center - step >= lower && 
                        arr[center - step].CompareTo(value) == 0) center -= step;
                }
                return center;
            }
    }
    return arr.GetLowerBound(0) - 1;
}

conduct a binary search to find the element. Return the index upon successful search, else return -1.

java code:
static int search_sortedarr(int num, int [] arr, int start_index,int end_index){
int mid = start_index + (end_index-start_index)/2;
if(end_index<=start_index && num!=arr[mid]) return -1;
if(num == arr[mid]) return mid;
else if(num>arr[mid]) return search_sortedarr(num, arr, mid+1, end_index);
else return search_sortedarr(num, arr, start_index, mid);
}

now, make a call to search_sortedarr(k,arr,0,arr.length-1) in the main.