How do I modify a standard binary search to return the one's complement of the next highest number?

November 26, 2004 9:00 AM

Algorithm help: C# uses a version of binary search wherein if the desired number is not found, instead of returning -1 it returns a number who's one's complement is the index of the next largest number in the collection.

I'm trying to recreate this in Java -- How do I modify a standard binary search to return the one's complement of the next highest number? [more inside]

It's been a few years since first year CS, I'm afraid, and I can't find this using Google.

I think the correct approach is to return -1*high, or return -1 if the array size is 0, but I keep getting inconsistencies.

posted by krunk to Computers & Internet (16 answers total)

binary xor the next highest number with -1.
posted by andrew cooke at 9:11 AM on November 26, 2004

ii = 25;
jj = -1*ii;

printf("%x\n", jj);

jj = -1^ii;

printf("%x\n", jj);

produces...
ffffffe7
ffffffe6

you want the ffffffe6 version, i believe.

(http://users.powernet.co.uk/eton/kandr2/krx304.html)

on preview... cooke beat me.
posted by sleslie at 9:18 AM on November 26, 2004

Excellent, thanks -- using AskMe is much easier than spending 10 seconds actually thinking about the problem. It's like multi-threading!

As an aside, why isn't this trick taught more often? I did 6 years and 2 degrees in CS, and never came across this. Very useful. No one teaches the triple-XOR trick for swapping variable values either.
posted by krunk at 9:41 AM on November 26, 2004

Why isn't this trick taught more often?

Trickiness is not a desirable characteristic. Any time or resources saved by the implementation are usually insignificant compared to the time and resources lost trying to understand or maintain someone's too-clever code. "Trickiness" is sometimes necessary to obtain the desired result, but one must be willing to accept the price in maintainability.
posted by SPrintF at 11:11 AM on November 26, 2004

well, it's not really a "trick", persay -- it's a one-line extension to a common routine, thus doubling its usefulness.

I think "ingenuity" would be more apt, and that is something that should most definitely be taught more often. It's things like that this that are savoured by graphics coders and their ilk.

which is, conveniently, what I'm doing right now ;^)
using this lets me save doing a linear search 20 times a second.
posted by krunk at 11:54 AM on November 26, 2004

there's a book with this kind of thing (obscure details about bit manipulation, efficient implementations of multiplies etc), published by o'reilly.
[searches around...]
here you go. it's not as interesting as it looks though (imho).

i'm not sure what you're talking about when it comes to learning. if you mean returning the 1s complement of the next value, that seems pretty unhelpful, but obviously you've got a use for it (can you explain why it's useful - i'd like to know, becasue i often write data containers that could return things like this if it were useful).

anyway, back on subject, if you mean knowing that 1s complement is the xor with -1 then i don't think it's the kind of thing you can teach. once you know what xor is, and that -1 is stored as all ones (ie that most languages use 2s complement) then it's just a case of being able to put 2 and 2 together. i don't think you can teach people how to do that - it's just the ability to find solutions starting with what you know. i certainly didn't "know" the answer until i thought about what was needed and worked it out.
posted by andrew cooke at 1:13 PM on November 26, 2004

oh. that link may not be public (work has access to safari). the book is "hacker's delight" by henry s warren jr.
posted by andrew cooke at 1:14 PM on November 26, 2004

it's useful because now I can use binary search to not only find where an item is in an array so I can remove it, but it now lets me find where to insert a new item into an array.

a standard binary search returns -1 if the element isn't in the array, but this version returns the one's complement of the index of the next highest element.

taking this value, then performing a one's complement on it, gives you the index of where to insert the value into the array -- O(log n) complexity.

the alternative is to do a sequential search, which on average would be O(n) complexity.

[note: I always assumed that sequential search was O(n/2), but since it grows linearly with the size of the array, it is O(n)]

here's the code, if you're interested:

	public static int binarySearch(int[] array, int target)
	{
	    int high = array.length, low = -1, probe;
	    while (high - low > 1)
	    {
	        probe = (high + low) / 2;
	        if (array[probe] < target)br>
	            low = probe;
	        else
	            high = probe;
	    }
	    if (high == array.length || array[high]) != target)
	        return -1^high; //added the ^high
	    else
	        return high;
	}

posted by krunk at 1:40 PM on November 26, 2004

now that I've checked out that book you recommended, I think this is definitely true hacking - a combination of ingenuity and trickery :^)
posted by krunk at 1:44 PM on November 26, 2004

ah. ok, thanks.
posted by andrew cooke at 1:47 PM on November 26, 2004

oh, I forgot -- this is how you'd use the return value:

int insertPoint = binarySearch(selection_, index);
if (insertPoint < 0)br>
	myCollection.insert(~insertPoint, index);

----------
if insertPoint was >=0, then the object already exists in the array.

(I'm using an auto-expanding data structure)
posted by krunk at 1:48 PM on November 26, 2004

I'm using an auto-expanding data structure

aha! ok, now it's clear. thanks. :o)
incidentally, in that case, i would use a sorted set in java (but i've not used java for several years now, so that may all have changed).
posted by andrew cooke at 2:00 PM on November 26, 2004

(and it may not do everything you need, of course)
posted by andrew cooke at 2:04 PM on November 26, 2004

Clever but if you actually use this in code the next person who reads your code is going to have come to ask metafilter to figure out what's going on in the code.

Also, you're talking about saving on a binary search which is only going to cost log 2 n. If you're dealing with a large enough array to make the search costly, then it seems likely that any time saving gained by not repeating the search will be swamped by the cost of moving bits around for a subsequent insertion.
posted by rdr at 8:27 PM on November 26, 2004

I'm a bigger fan of writing the routine to do what you want it do and naming it appropriately. If you're trying to find a place to do an insert, write a routine to do that. If you're trying to binary search to find a element, do that. If you can write them both in one and then write two tiny wrappers to do the right thing, more power to you.
posted by plinth at 5:45 PM on November 27, 2004

yeah, but as long as you know that the binary search returns an answer < 0 if the item isn't found, then you're cool. it's just a standard binary search.br>
moving the bits around isn't a problem -- it's just updating 2 references when you insert the new item.

RE: sorted set. My code has to be Java 1.1 compliant, so I can't use it :^(
posted by krunk at 12:38 PM on November 28, 2004