Using Bsearch to Find Index for Inserting New Element into Sorted Array

Using bsearch to find index for inserting new element into sorted array

You can use the Enumerator object returned by each_with_index to return a nested array of [value, index] pairs and then conduct your binary search on that array:

a = [1,2,4,5,6]
new_elm = 3

index = [*a.each_with_index].bsearch{|x, _| x > new_elm}.last
=> 2

a.insert(index, new_elm)

EDIT:

I've run some simple benchmarks in response to your question with an array of length 1e6 - 1:

require 'benchmark'

def binary_insert(a,e)
  index = [*a.each_with_index].bsearch{|x, _| x > e}.last
  a.insert(index, e)
end

a = *1..1e6
b = a.delete_at(1e5)
=> 100001

Benchmark.measure{binary_insert(a,b)}
=> #<Benchmark::Tms:0x007fd3883133d8 @label="", @real=0.37332, @cstime=0.0, @cutime=0.0, @stime=0.029999999999999805, @utime=0.240000000000002, @total=0.2700000000000018> 

With this in mind, you might consider trying using a heap or a trie instead of an array to store your values. Heaps in particular have constant insertion and removal time complexities, making them ideal for large storage applications. Check out this article here: Ruby algorithms: sorting, trie, and heaps

Binary search and insert to sorted array of objects

There are three errors in your code:

Incorrect usage of Array.splice

Check the Array.splice docs

Return value

An array containing the deleted elements.

• If only one element is removed, an array of one element is returned.
• If no elements are removed, an empty array is returned.

Incorrect implementation of binary search

• what if you get first > last? You return -1 (incorrectly)

Incorrect handling of negative index returned by binary search

• you pass negative index to slice as start
• again, form docs (parameters: start):

If negative, it will begin that many elements from the end of the array.

• you insert target item one position before the end
• but it happens to be right position in your test case. Test is green :)

How to find the insertion point in an array bsearch() works on?

Its not clear from the question but possibly this is what you want:

You can do something like this to find the index in the array where bsearch () found the match.

if (bsearch_returned_address != NULL)
  index = (bsearch_returned_address - array_base_address)

EDIT

To know the location which the bsort last visited, check the below stuff out.

The good thing is that the manual says:

The compar routine is expected to have two arguments which point to the key object and to an array member, in that order, and should return an integer less than,
equal to, or greater than
zero if the key object is found, respectively, to be less than, to match, or be greater than the array member.

Therefore you can store the second argument inside the comparison function in a global variable, and in a case of the fail use the address in this variable, which points to the last location the bsearch function visited to find for a match.

For example:

A list with address and value:

[0x8d6010: 0][0x8d6014: 4][0x8d6018: 8][0x8d601c: 12][0x8d6020: 16][0x8d6024: 20][0x8d6028: 24][0x8d602c: 28][0x8d6030: 32][0x8d6034: 36]

Value to search

13

output

fmem: (nil)  //this is the memory location where it was found
last_mem1: 0x7fff8c8e6c54 //last val of 1st param of compare
last_mem2: 0x8d601c //last val of 2nd param of compare
*last_mem1: 13,        *last_mem2: 12

The sample compare function code is

static const int *last_mem1, *last_mem2;

static int
compmi(const void *a, const void *b)
{
    last_mem1 = a; last_mem2 = b;
    return *(int *)a - *(int *)b;
}

So you can insert after the address in last_mem2. Although there are terminal cases, if you find a key which is less than the first element, then last_mem2 will also have the address of the first element.

But how ever you have to shift the array elements to make place for the insertion, which will make the insertion complexity to O(n). You might want to improve performance by introducing some kind of lazy insertion, like make a separate unordered list, which is much smaller than your original list, and dump new elements there. When searching, perform bsearch in original list, and linear search in the dump. When the dump list grows past a certain threshold, you can merge the list by performing an insertion sort. But still, you can't be O(lg n).

Inserting elements from a sorted array into a BST in an efficient way

I see the following issues with your attempt:

1. In each recursive call you are going to insert a node. So for instance, also when you reach the first, left-most leaf. But this cannot be right. The first node insertion may have to happen completely elsewhere in the tree without affecting this leaf at all

2. There is no check that index runs out of bounds. The code assumes that there are just as many values to insert as there are nodes in the tree.

3. There is no provision for when the value is equal to the value of an existing node in the tree. In that case the value should not be added at all, but ignored.

4. In most languages index will be a local variable to the Algo function, and so updating it (with + 1) will have no effect to the index variable that the caller has. You would need a single index variable that is shared across all executions of Algo. In some languages you may be able to pass index by reference, while in other languages you may be able to access a more global variable, which is not passed as argument.

Algorithm

The algorithm to use is as follows:

Perform the inorder traversal (as you already did). But keep track of the previously visited node. Only when you detect that the next value to be inserted is between the values of those two nodes, you need to act: in that case create a new node and insert it. Here is how to detect where to insert it. Either:

1. the current node has no left child, which also means the previous node (in the inorder sequence) is not existing or is higher up the tree. In this case the new node should become the left child of the current node

2. the current node has a left child, which also means the previous node is in the left subtree and has no right child of its own. In that case, add the new node as right child of the previous node.

The Sentinel idea

There is a possibility that after visiting the last node in inorder sequence, there are still values to insert, because they are greater than the greatest value in the tree. Either you must treat that case separately after the recursive traversal has finished, or you can begin your algorithm by adding a new, temporary root to your tree, which has a dummy, but large value -- greater than the greatest value to insert. Its left child is then the real root. With that trick you are sure that the recursive logic described above will insert nodes for all values, because they will all be less than that temporary node's value.

Implementation in Python

Here is the algorithm in Python syntax, using that "sentinel" node idea:

def insertsorted(root, values):
    if not values:
        return root  # Nothing to do

    # These variables are common to all recursive executions:
    i = 0  # index in values
    prev = None  # the previously visited node in inorder sequence

    def recur(node):
        nonlocal i, prev  # We allow those shared variables to be modified here
        if i < len(values) and node.left:
            recur(node.left)
        while i < len(values) and values[i] <= node.value:
            if values[i] < node.value:
                newnode = Node(values[i])
                if node.left is None:
                    node.left = newnode
                else:
                    prev.right = newnode
                prev = newnode
            i += 1
        prev = node
        if i < len(values) and node.right:
            recur(node.right)
    
    # Create a temporary node that will become the parent of the root
    # Give it a value greater than the last one in the array
    sentinel = Node(values[-1] + 1)  
    sentinel.left = root
    recur(sentinel)
    # Return the real root to the caller
    return sentinel.left

Array#bsearch in Ruby returns nil if the 0 index value is the ONLY value that meets the condition

Part of the documentation for Array#bsearch is the following requirement:

You can use this method in two modes: a find-minimum mode and a find-any mode. In either case, the elements of the array must be monotone (or sorted) with respect to the block.

In your example you are using find-minimum mode. From there we look at some of your inputs you've used and see if they are monotone or not.

# Monotone increasing, allowed
ary = [0, 4, 7, 10, 12]                                                                        

# Not monotone, not allowed                                                                                            
ary = [14, 3, 7]                                                                               

# Monotone decreasing, allowed
ary = [14, 13, 7]                                                                               

Return the insert position of an element into a sorted array with Binary Search Recursion

Your mistake is removing array[middle] from split, when bs(left,middle-1). Instead, you need use bs(left,middle) and bs(middle+1,right). I added print to recursive calls and found it easily.

public static int bs(int[] array, int left, int right, int elem) {
    System.out.println("["+left+", "+right+"]");
    if (left > right) {
        return left;
    } else {
        int middle;
        middle = (left + right) / 2;
        if (left == right) { // used to return the insert position
            return left;
        } else if (elem > array[middle]) {
            return bs(array, middle + 1, right, elem);
        } else if ((elem < array[middle])) {
            return bs(array, left, middle, elem); //<-- was: middle-1
        } else {
            return middle; // element existed into array
        }
    }
}

Also I think this style would be better;)

public static int bs2(int[] array, int left, int right, int elem) {
    System.out.println("["+left+", "+right+"]");
    if (left >= right)
        return left;

    int middle;
    middle = (left + right) / 2;
    if (elem > array[middle])
        return bs(array, middle + 1, right, elem);
    if ((elem < array[middle]))
        return bs(array, left, middle, elem); //<--- was: middle-1
    return middle; // element existed into array
}

---

Related Topics