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]+" ");
}
Deadbeef
  • 1,499
  • 8
  • 20
pallav dhar
  • 1
  • 1
  • 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 05 '20 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 05 '20 at 16:04

2 Answers2

0

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

3asyPe
  • 254
  • 1
  • 6
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]
Nowhere Man
  • 19,170
  • 9
  • 17
  • 42
  • Forgive me, but how does this explain why the binary search isn't working for the approach in the Question? – Scratte Jul 05 '20 at 14:10
  • That was [answered before](https://stackoverflow.com/a/62741419/13279831) - library implementation of binary search works with sorted arrays. Actual OP's task consists in _rearranging_ the input array. – Nowhere Man Jul 05 '20 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 05 '20 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 05 '20 at 15:21