CODEWITHSUNDEEP
javaarrayssearchintegerbinary-search
user3845574
user3845574

Reputation: 41

Java Leftmost Binary Search

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.

Upvotes: 0

Views: 1938

Answers (2)

RP-
RP-

Reputation: 5837

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;
}

Upvotes: 1

Constantinos
Constantinos

Reputation: 1208

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;
}

Upvotes: 0

Related Questions