CODEWITHSUNDEEP
javabinary-search
tamiresserafim
tamiresserafim

Reputation: 21

Binary search that returns the index where the value should be inserted

I need to do a binary search that in addition to the normal function, when the value is not found it returns the index where I must insert a new element for sorting. In the code below, the second for works to do a search of the index where the element to be exchanged. I need to do a function that replaces this with a binary search. What would this method look like?

void insertion (int n, int v[])
{
   for (int j = 1; j < n; ++j) {
   int x = v[j];
   int i;
// this for searches where the value should be inserted
   for (i = j-1; i >= 0 && v[i] > x; --i) 
        v[i+1] = v[i];
        v[i+1] = x;
   }
}

I know that normal binary search is like this. What do I need to change?

    static int BinarySearchR (int [] array, int l, int r, int key) {
        int mid = ((r - l) / 2) + l;
        if (array[mid] == key) return mid;
        else if (array[mid] > key) return BinarySearchR(array, l, mid- 1, key);
        else if(array[mid] < key) return BinarySearchR(array, mid + 1, r, key); 
        return -1;
    }

Upvotes: 1

Views: 2050

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109613

Arrays.binarySearch provides this:

int foundPos = Arrays.binarySearch(array, key);
if (foundPos < 0) {
    // Not found:
    int insertPos = ~foundPos;
}

A positive result gives the found position/index. A negative result gives the one's complement of the insert position.

An other advantage are the many overloads of this function for other types, and other variants for subarrays.

Upvotes: 0

tamiresserafim
tamiresserafim

Reputation: 21

With some adjustments it worked:

public static int BuscaBinariaI(int [] arr, int l, int r, int n) {
        int mid = 0;
            while(l < r){
                mid = l + (r - l)/2;
                if(arr[mid] == n) {
                    return -1;
                } 
                else if(arr[mid] > n){
                    r = mid - 1;
                    BuscaBinariaI( arr, l, r, n);
                }
                else {
                    l = mid + 1;
                    BuscaBinariaI( arr, l, r, n);
                }
            }
            if (mid>=arr.length) return arr.length;
            else if(arr[mid] > n) return mid ;
            else return mid + 1;
    }

Upvotes: 1

Related Questions