Click here to Skip to main content
15,844,498 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
How can I use the Binary search algorithm to display duplicates of a sorted array, with all their indexes. I have a working Binary search algorithm but cannot display all duplicates. Could anyone help and explain how this can be achieved?
Thank You.

What I have tried:

Searching Algorithm:
C#
static int BinarySearch(int[] arr, int key)
        {
            int minNum = 0;
            int maxNum = arr.Length - 1;

            while (minNum <= maxNum)
            {
                int mid = (minNum + maxNum) / 2;
                if (key == arr[mid])
                {
                    return (++mid);
                }
                else if (key > arr[mid])
                {
                    minNum = mid + 1;
                }
                else
                {
                    maxNum = mid - 1;
                }
            }
            return -1;
        }
Posted
Updated 18-May-23 6:25am

Quote:
How can I use the Binary search algorithm to display duplicates of a sorted array, with all their indexes.

Short answer: you don't, it is not its purpose.
A binary search only gives you the position of the value you want, or the position of 1 of them if duplicated.
To display all duplicates and indexes, you need to do a secondary search around the position returned by binary search routine.
C++
return (++mid);

By the way, why are you adding 1 to the position of matching element ?
 
Share this answer
 
Comments
Richard MacCutchan 12-Mar-20 5:16am    
Another repost.
I did it as follows :
int arr[]= {1,2,5,5,5,6,8,9,10}; , number =5;
find first occurence and last occurence of given `number`
Java
helper_rec(arr, number, firstindex , lastindex){

	int mid = firstindex + lastindex/2;
	//base case
	if(arr[mid] == number){
		int tempmid=mid;
		while(arr[tempmid]==number && mid >=0){
			tempmid--;//2
		}
		if(arr[tempmid+1]==number{
			first = arr[tempmid+1];
		}
		tempmid =mid;//0
		while(arr[tempmid]==number && mid< arr.length){
			tempmid++;
		}
		if(arr[tempmid]==number){
			second =arr[tempmid-1];
		}
		return;
	}
	
	//recursive
	
	if(mid< number ){
		helper_rec(arr, number, mid+1, lastindex);
	}
	else{
		helper_rec(arr, number , 0 , mid);
	}
	return;
}
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900