Property

Showing posts with label Amazon. Show all posts
Showing posts with label Amazon. Show all posts

Wednesday, December 10, 2014

Find the first occurrence of an integer in an array of sorted integers in O(logn).

Given a sorted array, where exists duplicated integers, find the first occurrence of the target integer?

code:
#include <stdio.h> 
int arr[100],mid,l,r,len,position,i,target;
int binarySearchFirstOccur();
int main()
{ 
 printf("Enter number of elements\n");
 scanf("%d",&len);
 printf("Enter %d integers\n", len);
 for ( i = 0 ; i < len ; i++ )
      scanf("%d",&arr[i]);
 
 printf("Enter value to find\n");
 scanf("%d",&target);
 position=binarySearchFirstOccur();
    if( position!= -1)
     printf(" Given integer is present at %d index in array",position);
    else
     printf(" Given integer is not present in array");
  return 0;
}

int binarySearchFirstOccur()
{
 int l=0,r=len-1;
 int mid=(l+r)/2;
 
 while(l+1!=r)  //l+1==r => arr[l]<target and arr[r]>=target and l<r     
 {      
  if(arr[mid]<target)  //target is in the right
     l=mid;
  else
   r=mid;  
  mid=(l+r)/2;
 }
 
 if(r<len||arr[r]==target)
 return r;  //r is the first occurrence index
 else 
 return -1;    //didnt find the integer
}

output:-
Enter number of elements
10
Enter 10 integers
1 2 3 4 5 6 7 8 8 9
Enter value to find
8
Given integer is present at 7 index in array

let me demonstrate this for you:
first initialize l,r and mid
l=0
r=9
mid=0+9/2=4

value:  1  2   3   4   5   6   7   8   8   9
index:  0  1   2   3   4   5   6   7   8   9
             l                  m                      r
arr[mid]<target
arr[4]<8
5<8
yes,therefore change value of l,
l=mid
l=4
r=9
mid=(4+9)/2=6

value: 1  2   3   4   5   6   7   8   8   9
index: 0  1   2   3   4   5   6   7   8   9
                                      m            r
arr[mid]<target
arr[6]<8
7<8
yes,therefore change value of l,
l=mid
l=6
r=9
mid=(6+9)/2=7


value: 1  2   3   4   5   6   7   8   8   9
index: 0  1   2   3   4   5   6   7   8   9
                                          m        r
arr[mid]<target

arr[7]<8
8<8
no,therefore change value of r,
r=mid
r=7
l=6
mid=(6+7)/2=6

now we are done with first occurrence
note in while loop condition is

while(l+1!=r)
not
 while(l<r)

because it will go to infinite loop because as you can see we are storing index in r. Therefore
l<r will always true.

All Rights Reserved. 2014 Copyright SIMPLITONA

Powered By Blogger | Published By Gooyaabi Templates Designed By : BloggerMotion

Top