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

Question

using bsearch () in C (standard library), you can quickly find an entry in a sorted array.

However, how can I figure out where to insert a new record (using the standard library)?

bsearch () specifically checks to see if the key of the element found is equal to the passed key, and if not, it returns NULL - therefore, cannot use this.

Answer 1

This is not clear from the question, but maybe this is what you want:

You can do something similar to find the index in the array where bsearch () matches.

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

EDIT

To find out the location the last bsort visitor visited, check out the material below.

It’s good that the manual says:

It is assumed that the comparison procedure has two arguments that point to the key object and to the array element in this order and should return an integer less than, equal to or greater than zero if the key object is found, respectively, less to match or be more than an array element.

Therefore, you can save the second argument inside the comparison function in a global variable, and in case of failure, use the address in this variable, which indicates the last location that the bsearch function visited to find for matching.

For instance:

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] 

Search Value

 13 

Exit

 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 

Sample Comparison Function Code

 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; } 

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

But no matter how you transfer the elements of the array to do this, to make the complexity of inserting O(n) . You can improve performance by introducing some kind of lazy insert, for example, make a separate unordered list, which is much smaller than your original list, and discard new items there. When searching, do bsearch in the source list and linear search in the dump. When the dump list exceeds a certain threshold, you can combine the list by sorting the insert. But still you cannot be O(lg n) .

Answer 2

Not sure what you mean by "calculating the insertion point"; you create an array and then sort it with qsort() , then do a (many) search with bsearch() .

In other words: for typical use, you do not need to implement array sorting, since the standard library also contains functionality.

Not sure about halving here.

UPDATE . From the comment, it seems that you are worried about doing inserts into the array from which you are also searching. I would recommend looking at another data structure that is more insert-friendly, like a hash table. Without relying on sorting for quick searches, a hash table may work better. Inserting into an array involves moving all subsequent elements, which is also quite expensive and not required for, for example, a hash table.

UPDATE 2 . To actually try to answer your question, if you have a bsearch() -component function comparator() for your array of n entries, the index for the new ni element must be specified as follows:

 size_t i; for( i = 0; i < n && comparator(&ni, array + i) >= 0; ++i ) ; /* Grow array, copy i..n to (i+1)..(n+1), insert ni at i. */ 

Answer 3

Since the insert causes the tail of the array to be copied, the time is O (n). Thus, a simple linear search will not slow down your code. You can even copy elements during the search if you start the search from the end of the array.

Answer 4

This is where @phoxis' answer improves, which will make the code thread safe and repetitive, avoiding any global variables. The trick is to use the key itself to store the last visited address.

bsearch_insertion.h

 #include <stdlib.h> #ifndef BSEARCH_INSERTION_H #define BSEARCH_INSERTION_H /* Just like bsearch(3), but return a pointer to the element after which * the key would need to be inserted in order to maintain sorted order. */ void *bsearch_insertion( const void *key, const void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); #endif /* BSEARCH_INSERTION_H */ 

bsearch_insertion.c

 #include "bsearch_insertion.h" typedef struct { const void *key; int (*const compar)(const void *, const void *); void *last_visited; } bsearch_insertion_state; static int bsearch_insertion_compare(const void *a, const void *b) { bsearch_insertion_state *state = (bsearch_insertion_state *) a; state->last_visited = (void *) b; return state->compar(state->key, b); } void *bsearch_insertion( const void *key, const void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)) { bsearch_insertion_state state = {key, compar, NULL}; bsearch(&state, base, nel, width, bsearch_insertion_compare); return state.last_visited; } 

Example: test.c

 #include <stdio.h> #include "bsearch_insertion.h" static int cmp(const void *a, const void *b) { int aint = *(const int *)a; int bint = *(const int *)b; return aint - bint; } int main(int argc, char **argv) { int data[] = {0, 1, 2, 3, 5}; int key = 4; void *result = bsearch_insertion( &key, data, sizeof(data) / sizeof(data[0]), sizeof(data[0]), cmp); /* Should print "Insertion point: 3" */ printf("Insertion point: %d\n", (int *)result - data); return 0; }