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
                               l        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
                                        l   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.

SHARE