0

Given an array of elements of length N, ranging from 0 to N – 1. All elements may not be present in the array. If element is not present then there will be -1 present in the array. Rearrange the array such that A[i] = i and if i is not present, display -1 at that place

So that is the question, but my binarySearch is not working, why?

for(int i = 0; i < size; i++) {
            
        int res = i;
        //  System.out.println(Arrays.binarySearch(arr,res));
        int result = Arrays.binarySearch(arr,res);
    
            if(result == -1)
                arr[i] = -1;
            else {
                arr[i] = i;
            }
}
for(int i = 0; i < size; i++) {
    System.out.print(arr[i]+" ");
}
2
  • I would not try to find values in the array. I would move thought the array and every time I see a value that is not -1, I would swap that value with the value that is at the corresponding index. So if I find arr[2] is 4, I will swap the values between a[2] and a[4].
    – Scratte
    Jul 5, 2020 at 13:54
  • Can you edit your question and post the declaration of arr? Can you also post sample values for arr and what values arr would contain after the re-arranging?
    – Abra
    Jul 5, 2020 at 16:04

2 Answers 2

0

Binary search works only with sorted arrays. Try using a different search algorithm

0

If you can use additional array, the solution may be as follows:

  1. Create resulting array
  2. Fill resulting array with -1
  3. Iterate over input array and fill appropriate numbers in the resulting array.
    // input array
    int[] arr = {-1, 2, 3, 0};
        
    // prepare new resulting array
    int[] res = new int[arr.length];
    // fill with -1
    // Arrays.fill(res, -1);  // use this shortcut if you're allowed to use library
    for (int i = 0; i < res.length; i++) {
        res[i] = -1;
    }
    // rearrange
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != -1) {
            res[arr[i]] = arr[i];
        }
    }
    System.out.println("input data: " + Arrays.toString(arr));
    System.out.println("rearranged: " + Arrays.toString(res));

Output:

input data: [-1, 2, 3, 0]
rearranged: [0, -1, 2, 3]

Update

Recursive solution without using extra array:

public static void test() {
    int[] arr = {-1, 4, 2, 0, 1, 3};
    System.out.println("input data: " + Arrays.toString(arr));
        
    // rearrange
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != -1 && arr[i] != i) {
            swapAtIndex(arr, i);
        }
    }
    System.out.println("rearranged: " + Arrays.toString(arr));
}

private static void swapAtIndex(int[] arr, int i) {
    int t = arr[i];
    if (t != -1 && t != i) {
        int t2 = arr[t];
        arr[t] = t;
        arr[i] = t2;
        if (t2 != -1) {
            swapAtIndex(arr, i); // continue swapping at the same index
        }
    }
}

output:

input data: [-1, 4, 2, 0, 1, 3]
rearranged: [0, 1, 2, 3, 4, -1]

For the input array without -1, you'll get a sorted array after rearrangement:

input data: [5, 4, 2, 0, 1, 3]
rearranged: [0, 1, 2, 3, 4, 5]
4
  • Forgive me, but how does this explain why the binary search isn't working for the approach in the Question?
    – Scratte
    Jul 5, 2020 at 14:10
  • That was answered before - library implementation of binary search works with sorted arrays. Actual OP's task consists in rearranging the input array. Jul 5, 2020 at 14:30
  • I see. I find it not to be a very thorough answer though. Meaning if I didn't understand why, then it would not have helped me. I would have then asked myself: But why doesn't it work with unsorted arrays? I think the answer to this is in the proposed duplicate.
    – Scratte
    Jul 5, 2020 at 14:32
  • Binary search involves finding a number in a sorted array. For example if you had [-5, -1, 3, 7, 11, 13, 19] and you are looking for 11. take the median of the array, which is 7, compare it to 11 and you know to look for somewhere in [11, 13, 19] Take the median and repeat until you find the number.
    – Deadbeef
    Jul 5, 2020 at 15:21

Not the answer you're looking for? Browse other questions tagged or ask your own question.