Java Leftmost Binary Search

Question

I am trying to modify a Recursive Binary Search function so that it will find the leftmost index of the element given the array contains multiples of that element.

import java.util.*;
import java.util.Arrays;
import java.io.File;
import java.io.IOException;

public class LeftmostBinarySearch {

    private static int myBinarySearch(int key, int[] a, int lo, int hi) {
    if (lo > hi) {
        return -1;
    }
    int mid = lo + (hi - lo) / 2;
    if (key < a[mid]) {
        return myBinarySearch(key, a, lo, mid - 1);
    } else if (key > a[mid]) {
        return myBinarySearch(key, a, mid + 1, hi);
    } else {
        return mid;
    }
}

    public static int myBinarySearch(int key, int[] a) {
    return myBinarySearch(key, a, 0, a.length - 1);
}

    public static void main(String[] args) throws IOException {
        String fileName = args[0] + ".txt";
        System.out.println(fileName);
        Scanner scanner = new Scanner(new File(fileName));
        int[] data = new int[7];
        int i = 0;
        int j = 0;

        while (scanner.hasNextInt()) {
            data[i] = scanner.nextInt();
            i++;
        }
        Arrays.sort(data);
        System.out.format("%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s", " 0",
                "  ", " 1", "  ", " 2", "  ", " 3", "  ", " 4", "  ", " 5", "  ", " 6\n");
        System.out.format("%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s%2s", data[j],
                "  ", data[j + 1], "  ", data[j + 2], "  ", data[j + 3], "  ",
                data[j + 4], " ", data[j + 5], "  ", data[j + 6] + "\n");

        int input = new Scanner(System.in).nextInt();

        while ((Integer) input != null) {
            int key = input;
            System.out.println(data[0]);
            if (myBinarySearch(key, data) != -1) {
                System.out.println(input + " found: "
                        + myBinarySearch(key, data));
            }
            input = new Scanner(System.in).nextInt();
        }
    }
}

The output I have gotten from this is:

C:\Users\Shirley\algs4>java LeftmostBinarySearch mydata
 0   1   2   3   4   5   6
10  20  20  30  40  40  40
10
10 found: 0
20
20 found: 1
30
30 found: 3
40
40 found: 5

I have tried changing how I calculate mid to (hi + lo - 1)/2 and it works for 40, gives index 3, but for 20 it gives index 2.

Vitaliy Terziev · Accepted Answer · 2019-05-07 20:32:05Z

1

You need to check if(key == a[mid]). If it is equal, you need to check if the last element in left portion is same until you find a different element.

The following check should come before you branch left or right

if (key == a[mid]) {
    while (--mid >= 0) {
        if (key != a[mid]) {
            break;
        }
    }
    return ++mid;
}

edited May 7, 2019 at 20:32

Vitaliy Terziev

6,7313 gold badges19 silver badges29 bronze badges

answered Sep 16, 2014 at 23:41

RP-

5,8372 gold badges32 silver badges48 bronze badges

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

1 Comment

Vitaliy Terziev Over a year ago

this however is introducing yet another pair of decision blocks and loop and adding to the algorithm's complexity, is there optimized way to do this using the 'standard' implementation or one should use Hermann Bottenbruch's alternative procedure -> en.wikipedia.org/wiki/…

Constantinos · Accepted Answer · 2014-09-16 23:49:45Z

0

The problem is with the last line:

else return mid;

Your list contains duplicates so mid may not be the leftmost match. So try:

else {
  while(--mid>=0) {
    if (a[mid]!=key) break;
  }
  return mid+1;
}

answered Sep 16, 2014 at 23:49

Constantinos

1,20812 silver badges18 bronze badges

1 Comment

user3845574 Over a year ago

That did it. I wasn't thinking about doing it at the end. Thanks a lot!

Collectives™ on Stack Overflow

Java Leftmost Binary Search

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related