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.

0 comments: