I want to write a program to conduct a binary search and return all the occurrences of a number to the user. I succeeded in coming up with a binary search method but I don't know how to make return all the occurrences of the number. Here is my code

/*
	 *A method which searches for the position of a number
	 *specified by the user
	 *@param target, the number the user is looking for
	 *@return the position(s) in which the number is found
	*/
	int binarySearch(int target)
	{
		int left = 0;
		int right = userArray.length - 1;
		while (left <= right)
		{
			int midPoint = (left + right)/2;
			if (userArray[midPoint] == target)
			{
				for (int i = 0; i <= userArray.length; i++)
				{
					
				}
				return (midPoint + 1);
			}
			else if (userArray[midPoint] < target)
				left += 1;
			else
				right -= 1;
		}
		return -1;
	}

Well since you found the number you know one of the occurrences of the number.
Assume this:
You are looking for '3'

1 2 3 3 3 4 5

And you find the position of the "Red" 3. So all the others 3s will be either left or right from the position you found. Of course your algorithm might find this:

1 2 3 3 3 4 5

or this:

1 2 3 3 3 4 5

You need to search the neighbor positions to see if the target is there. Maybe another while loop before you return.

Sorry, I was absent for some days. I tried what you said and I came up with the following code. My problem is that it only returns me one position. I call it also to print the positions in the main class in addition to calling it here. I am kind of lost. Please help me finish it. Here is my code

/*
	 *A method which searches for the position of a number
	 *specified by the user
	 *@param target, the number the user is looking for
	 *@return the position(s) in which the number is found
	*/
	int binarySearch(int target)
	{
		int left = 0;
		int right = userArray.length - 1;
		while (left <= right)
		{
			int midPoint = (left + right)/2;
			System.out.println("The middle is at position " + midPoint);
			System.out.println("Checking position... " + midPoint);
			if (userArray[midPoint] == target)
				return (midPoint + 1);
			else if (userArray[midPoint] < target)
				left += 1;
			else
				right -= 1;
		
		int first = 0, last = 0;
		for (int counter = 1; counter > 0; counter++)
		{
			if (userArray[counter] == target)
				first = midPoint - counter;
			else 
				counter = -1;
		}
		
		for (int j = midPoint; j > 0; j++)
		{
			if (userArray[j] == target)
				last = midPoint + j;
			else 
				j = -1;
		}
		
		for (int i = first; i < last; i++)
			System.out.println("Your number " + target + " is found in position(s) " + (i + 1));
	
		}
				return -1;
	}

I think you should keep your code they way it was and return the index where the target element was found. Without increasing it by 1. In your methods you should always return indexes the way they are. 0 based. In java indexes begin with zero. Don't change that. If you want to add 1 do it after your program returns the value when you print int.

Not to talk about your problem. Keep the code the way it is and find the index where the target is. Then outside the while loop, after you get the index, search the neighbor elements to see if they are equal with the target.
First start checking the ones that are lower than the index and keep reducing the index until you find something that is not equal:

int index;
while () {

}
// found target at index
int tempIndex = index;
while ( ([B]tempIndex>=0[/B]) && (userArray[tempIndex]==target) ) {
  System.out.println("Found at: "+tempIndex);
  tempIndex[B]--[/B];
}

// do the same by increasing the index. Careful with the expression at the while loop

All it is left to decide now is what you want your method to return and how.

Thanks, I modified my code to what you said but I used a for loop instead. It works quite well now. Thanks for your aid.

Thanks for your aid. I modified my program to what you said but used a for loop instead. It works. Thanks.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.