Find the largest index occurrence of a number using binary search

Question

This code, generates a random number, sorts it in ascending order and does the binary search to find a target value. MY QUESTION IS HOW DO I MODIFY THIS CODE TO FIND THE LARGEST INDEX OF THE GIVEN TARGET. For example the array has { 1, 2 , 3, 5, 5, 5, 5}, the target is 5, so the output should be 6 instead of 3. Thankyou.

    import java.util.*;
    public class Sort
    {
        public static void main(String args[])
        {
            Scanner in = new Scanner(System.in);
            System.out.print("How many numbers do you want? ");
            int howMany = in.nextInt();
            int [] myArray =  getSortedRandomArray(howMany);
            System.out.print("\nFor what value would you like to search? ");
            int target = in.nextInt();
            int index = bsearch ( myArray, target);
            if (index >= 0)
            {
                System.out.println("The value " + target + " occurs at index " + index);
            }
            else
            {
                System.out.println("The value " + target + " does not occur in the array. ");
            }   
        }

  public static int bsearch(int[] arr, int key)
    {
    int lo = 0, hi = arr.length - 1;
    {
        while (lo < hi) 
        {
            int mid = (lo + hi) / 2;
            if (arr[mid] <= key)
                lo = mid + 1;
            if (arr[mid] > key)
                hi = mid;
        }
        if (arr[lo] == key) {
            return lo;
        }
        else if ((arr[lo] != key) && (arr[lo-1] == key)){
            return lo - 1;
        }
        else{
        System.out.print("The value " + key + " does not occur in the array. "); 
    } 
        return -1 ;
    } 
   public static int[] getSortedRandomArray (int howMany)
    {
        int[] returnMe = new int [howMany];
        Random rand = new Random();
        for (int i = 0; i < howMany ; i++) 
            returnMe[i] = rand.nextInt(Integer.MAX_VALUE) + 1;
        for (int i = 1; i <= (howMany - 1); i++)
        {
            for (int j = 0; j <= howMany - i -1; j++)
            {
                int tmp = 0;
                if (returnMe[j] > returnMe[j+1])
                {
                    tmp = returnMe[j];
                    returnMe[j] = returnMe[j + 1];
                    returnMe[j + 1] = tmp; 
                }   
            }  
        }
        System.out.print("Here is a random sorted array: ");
        for ( int i = 0; i < howMany; i++)
            System.out.print(returnMe[i] + " ");     
        return returnMe;
    }

Me?? lol no. Im sorry if that was not polite sir! @OusmaneMahyDiaw — rockster
– rockster, Commented Apr 18, 2017 at 21:47
there is no problem, it's just unusual to write everything is CAPITALS. — Ousmane D.
– Ousmane D., Commented Apr 18, 2017 at 21:47
Well, you've found the index of one element with that value. And all of the other elements with the same value are next to each other. So... how do you think you could find it? — Andy Turner
– Andy Turner, Commented Apr 18, 2017 at 21:47
@AndyTurner I thought of using a loop , but wouldn't that be inefficient if there were like 100 numbers with all the same target value? — rockster
– rockster, Commented Apr 18, 2017 at 21:50
@rockster as many as that? :) Remember, correctness is always more important than speed. Do it the easy way, and worry about the performance later when profiling shows that it is a problem. — Andy Turner
– Andy Turner, Commented Apr 18, 2017 at 21:59

leonz · Accepted Answer · 2017-04-18 23:04:55Z

1

You can do this by modifying the binary search algorithms code like this:

 public static int bsearch(int[] arr, int key) {
    int lo = 0, hi = arr.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] <= key)
            lo = mid + 1;
        if (arr[mid] > key)
            hi = mid;
    }

    if (arr[lo] == key) {
        return lo;
    }
    else {
        return lo - 1;
    }
}

This code instead searches for the first number larger than key. That can be any number, 6 or 10000, it doesn't matter. As you can see, if arr[mid] is equal to key, the code will still run on the interval [mid, hi]. Why those two returns at the end? Well if input array is like the one you gave, lo will end being the index of the last 5, but if we add another number at the end of input array, lo will be index of the number behind the last 5. Therefore, we have 2 different cases.

Also, you can't do it with a linear loop like other answers, because that reduces the algorithm to O(n) and it ends just being a linear search on a reduced array.

edited Apr 18, 2017 at 23:04

answered Apr 18, 2017 at 22:49

leonz

1,1273 gold badges10 silver badges32 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

rockster Over a year ago

Thankyou for the explanation too :) it helped a lot

leonz Over a year ago

No problem. Glad to help. I suggest you play around with this kind of algorithm now, if you want to learn more. If you do want, here's something interesting to do: modify the algorithm so that it works even if key is not in arr, for example when arr = {1, 3, 6, 8} and key = 5.

rockster Over a year ago

I used this code(edited in the question under bsearch) and it worked if there wasn't the number in the array but when the array is{ 5,6,9,9,9,9..} and the target is 4. It gives an error saying arrayIndexOfBoundException at else if ((arr[lo] != key) && (arr[lo-1] == key)){ @leonz

James · Accepted Answer · 2017-04-18 22:17:05Z

If you update your bsearch algorithm a little you can ask it to seek higher matches recursively. However whether this is more efficient than a linear loop would depend on what the input array looked like.

public static int bsearch(int[] arr, int key, int lo, int hi) {
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (arr[mid] == key) {
            System.out.println("The value " + key + " is found at " + mid);
            int higherResult = bsearch(arr, key, mid + 1, hi);
            if (higherResult < 0) {
                return mid;
            }
            return higherResult;
        }
        if (arr[mid] < key) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Collectives™ on Stack Overflow

Find the largest index occurrence of a number using binary search

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related