0

So, I've been given a problem to implement a program that returns true if an array of sorted integers contains numbers greater than I but less than u, false otherwise.

I've identified that a quick sort algorithm would be a good way to sort the array, because I can't know how the user will enter it in - then, I feed the sorted array to binary search and find out if the array contains integers within the specified range. The problem is, I can't seem to be able to reason about this, since it is not one value I want to find here, but a range. Also, I want to implement this recursively if possible.

Here's what I have so far:

import java.util.Scanner;

class RangeBinarySearch {
    public static int[] quickSort(int[] unsortedArray, int left, int right) {
    int[] sortArray = unsortedArray;
    if (left >= right)
        return sortArray;

    int pivot = unsortedArray[(left + right) / 2];

    int i = left;
    int j = right;

    while (i <= j) {
        while (unsortedArray[i] < pivot)
            i++;
        while (unsortedArray[j] > pivot)
            j--;
        if (i <= j) {
            int temp = unsortedArray[i];
            unsortedArray[i] = unsortedArray[j];
            unsortedArray[j] = temp;
            i++;
            j--;
        }
    }

    if (left < j)
        quickSort(unsortedArray, left, j);
    if (right > i)
        quickSort(unsortedArray, i, right);

    return sortArray;
    }

    public static boolean withinRangeSorted(int[] sortedArray, int I, int u) {// This uses binary search

    int start = 0;
    int end = sortedArray.length - 1;
    int mid = sortedArray[(start + end) / 2];


        if (sortedArray[start] > u || sortedArray[end] < I)
            return false;
        else if (sortedArray[start] > I && sortedArray[end] < u)
            return true;

        else {
            // What to do here? I am stuck!

        }
    return false;
    }

    public static void main(String[] args) {
    int size;
    int inum;

    Scanner input = new Scanner(System.in);
    System.out.println("Enter the size of the array: ");
    size = input.nextInt();
    int[] unsortArray = new int[size];

    for (int i = 0; i < size; i++) {
        int c = i + 1;
        System.out.println("Enter element " + c + " to be added to the array: ");
        inum = input.nextInt();
        unsortArray[i] = inum;
    }

    int left = 0;
    int right = size - 1;

    int[] sortedArray = quickSort(unsortArray, left, right);
    int I; // greater than
    int u; // less than

    System.out.println("Enter range starting point: ");
    I = input.nextInt();
    System.out.println("Enter range end point: ");
    u = input.nextInt();

    boolean result = withinRangeSorted(sortedArray, I, u);
    System.out.println(result);
    }
}

The problem is, I just can't seem to figure out how to structure the withinRangeSorted method.

I am mainly confused about what sort of parameters should the method even take if I am searching for a value greater than I and less than u. I feel like I'm on the right track here, but I can't seem to be able to formulate the recursion properly.

Any help would be much appreciated.

CuriOne
  • 103
  • 3
  • 8
  • I dont get the task, should you just return true if ONE number exists that is between i and u? Or does every number need to be in that range? – Michael Nov 02 '14 at 22:04
  • `I` and `u` as boundaries make less sense to me than `l` and `u`. If the array is sorted to begin with, I might do a binary search for `l` and check whether there is a next higher value and how it compares to `u`. (but, then, "nothing compares 2u") – greybeard Nov 03 '14 at 05:52

4 Answers4

2

You just need to adjust the array boundaries based on your range check during the binary search. I am pretty sure that the arguments are meant to be l (lower) and u (upper). Note that I always treat ranges as inclusive-exclusive.

/**
 * Whether array has at least one element x such that l <= x < u.
 */
boolean withinRangeSorted (int[] array, int l, int u) {
    int start = 0;
    int end = array.length;
    while (start < end) {
        int current = (start + end) / 2;
        if (array[current] >= u) {
            end = current;
        } else if (array[current] < l) {
            start = current + 1;
        } else {
            return true;
        }
    }
    return false;
}

If you want to transform this into a recursive implementation, use start and end as arguments to a recursive helper. If you want the range not as inclusive-exclusive, adjust <, <= etc. and + 1, but check for off-by-one-errors.

Svante
  • 50,694
  • 11
  • 78
  • 122
1

As I understand all the integers in the array must be greater than i but smaller then u. So the implementation is simple:

boolean withinRange(int[] array, int lower, int upper) {

    for (int i : array)
        if (i <= lower && i >= upper)
            return false;
    return true;
}

I am not sure why the array needs to be sorted though unless the condition is there needs to be at least 1 number within that range and not all of them as I understand.

But if you really need to find out if it contains a number within specified range then you can use this simple method which tests for each number in the range if it is present in the array:

boolean containsNumberInRange(int[] array, int lower, int upper) {

    for (int i = lower + 1; i < upper; i++)
        if (Arrays.binarySearch(array, i) >= 0)
            return true;
    return false;
}

Btw you do not need to implement quick sort algorithm yourself unless it is part of homework as Arrays.sort(int[]) can be used instead which internally uses quicksort.

ps-aux
  • 11,627
  • 25
  • 81
  • 128
  • The binary search part is not optimal. `Arrays.binarySearch(array, lower)` already returns the successor, so you just have to check whether it is smaller than `upper`. The way you check for existence is wrong too, [from how I read the docs](http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html#binarySearch(int[],%20int)) you should check for `>= 0` – Niklas B. Nov 02 '14 at 22:50
  • Thanks for correction. I forgot that the returned value contains "would-be inserted" information. I dont understand what you mean by first part though. – ps-aux Nov 02 '14 at 23:06
  • Generally it is MUCH faster to process a sorted array than an array that is not sorted - so the time spent sorting it is well spent. See http://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array?rq=1 for more details. – Andersnk Nov 02 '14 at 23:06
  • @AndersNK I do not see the possibility for similar branching here as in the provided SO post. I tried this in Java on array of 1 milion integers and did not see any difference between sorted and unsorted array in term of time. In fact if I took into account also the sorting overhead it was highly inefficient in comparison to using the unsorted array. – ps-aux Nov 02 '14 at 23:29
  • I meant something like `int succ = Arrays.binarySearch(array, lower); return `succ >= 0 ? array[succ] < upper : -succ-1 < n ? array[-succ-i] < upper` – Niklas B. Nov 03 '14 at 08:07
0

You can simply try to go over the different possibilities:

// assuming ascending order   
boolean isWithinRange (int [] sortedArray, int min, int max)
{
    int minArr, maxArr;

    minArr = sortedArray [0];

    maxArr = sortedArray [sortedArray.length-1];

    // xxxx..[oooo].. OR  ..[oooo]..xxxx
    if (minArr > max || maxArr < min) return false;

    // ..xx[xxxx]xx..
    if (minArr >= min && maxArr <= max) return true;

    // ..xx[xxooo]..
    if (minArr >= min && minArr <= max) return true;

    // ..[oooxx]xx..
    if (maxArr >= min && maxArr <= max) return true;

    return false;
}
Khaled.K
  • 5,828
  • 1
  • 33
  • 51
0

If there are only few such queries, It's better to do complete search.We don't need to sort the array. But,if there are many such queries and we want to do them efficiently, There is a simple O(logn) algorithm for this problem. Using a binary search, we can find the first index whose value is >= u. Similarly by doing another binary search, we can find the first index >= l. If the two indices are same, check it Else return true.

saisandeep
  • 63
  • 1
  • 7