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:
output:-
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
because it will go to infinite loop because as you can see we are storing index in r. Therefore
l<r will always true.
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.
0 comments: