CODEWITHSUNDEEP
optimizationbinary-search
Piyp791
Piyp791

Reputation: 669

binary search optimization in terms of number of comparisons

recently I was asked this question in an interview. In binary search we have two comparisons one for greater than and other for less than the mid value. Can it be optimized in a way so that we need to check only once ?

Upvotes: 1

Views: 253

Answers (2)

user555045
user555045

Reputation: 64904

Yes, in several ways.

By doing a three-way comparison, which exists in some versions Fortran (see "arithmetic IF").

By playing tricks with the wording - in x86 (and others) assembly you can use one cmp but still use two branches.

By using the Deferred Detection of Equality trick.

Upvotes: 2

Femaref
Femaref

Reputation: 61427

No, you can't. While you can switch the operators around (e.g. instead of greater and less use greater and equal), you'll end up with two comparisions. In binary search, you actually have three results, if you compare for two of them and neither is true, it can only be the third one.

For example:

if (lookup < mid)
  searchLower();
else if (lookup > mid)
  searchUpper();
else
  found(lookup);

If you switch the operators around, the implicated one will change, but you'll always need two comparisions.

Upvotes: 2

Related Questions