Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Re: A binary search algorithm that searches for an element similar tothe key

Reply
Thread Tools

Re: A binary search algorithm that searches for an element similar tothe key

 
 
88888 Dihedral
Guest
Posts: n/a
 
      12-21-2011
On Wednesday, December 21, 2011 7:13:05 AM UTC+8, pozz wrote:
> I want to write the function binsearch_low() with the same interface of
> bsearch() standard function:
>
> void * binsearch_low (const void *key, const void *array, size_t count,
> size_t size, comparison_fn_t compare);
>
> This function should return a pointer to the element of the array that
> is the greatest among the element with a lower value than key. If no
> element lower than key exists, the function should return NULL.
>
> For example, if I have the array { 10, 12, 17, 20, 25, 30 }, the
> function should return NULL for key=8, 10 for key=11, 12 for key=12, 20
> for key=22, 30 for key=33.
>
> I started from a bsearch() implementation...
>
> void *
> binsearch_low (const void *key, const void *array, size_t count, size_t
> size, comparison_fn_t compare)
> {
> int left = 0, right = count - 1;
> while (left <= right) {
> const int mid = (left + right) / 2;

mid is a variable

> void *element = (unsigned char *)array + mid * size;

element is a pointer that stores address
> if (compare(key, element) > 0) left = mid + 1;

*element is of type unsigned char but element is of type void *

> else if (compare(key, element) < 0) right = mid - 1;
> else return (unsigned char *)array + mid * size;
> }
> return NULL;
> }
>
> ...and arrived to the following algorithm:
>
> void *
> binsearch_low (const void *key, const void *array, size_t count, size_t
> size, comparison_fn_t compare)
> {
> int left = 0, right = count - 1;
> while (left < right - 1) {
> const int mid = (left + right) / 2;
> void *element = (unsigned char *)array + mid * size;
> if (compare(key, element) > 0) left = mid;
> else if (compare(key, element) < 0) right = mid - 1;
> else return (unsigned char *)array + mid * size;
> }
> if (compare(key, (unsigned char *)array + left * size) < 0) {
> return NULL;
> } else if (compare(key, (unsigned char *)array + right * size) >= 0) {
> return (unsigned char *)array + right * size;
> } else {
> return (unsigned char *)array + left * size;
> }
> }
>
> Do you have any suggestions and/or improvements?


kind of lousy for programs that mix a pointer declared and
the type that a pointer points to
 
Reply With Quote
 
 
 
 
88888 Dihedral
Guest
Posts: n/a
 
      12-21-2011
I wrote a binary search in assembly in 386 20 years ago.

This is trivial. There were EAX, EBX, ECX, EDX and ESI, EDI which are 6
32 bit general registers and a stack that can be pushed and popped.

I suggest you store the array starting address in ESI and use EDI as a general
pointer in the heap.

A program in C code within 20 lines should be coded in assembly easily for professionals in any 32 bit cpu easily.

I'll warn any programmer that dare to use any lousy name of any variable
to be a pointer witout ptr* or p* in the name under my supervision.


Then I'll ask the programmer to convert the program into a specified assembly
to prove the programmer is not stealing codes form others and faking to be
his own works.





 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      12-21-2011
88888 Dihedral <(E-Mail Removed)> writes:

> I wrote a binary search in assembly in 386 20 years ago.
>
> This is trivial. There were EAX, EBX, ECX, EDX and ESI, EDI which are 6
> 32 bit general registers and a stack that can be pushed and popped.
>
> I suggest you store the array starting address in ESI and use EDI as a
> general pointer in the heap.
>
> A program in C code within 20 lines should be coded in assembly easily
> for professionals in any 32 bit cpu easily.
>
> I'll warn any programmer that dare to use any lousy name of any variable
> to be a pointer witout ptr* or p* in the name under my supervision.


How many programmers are there under your supervision?

> Then I'll ask the programmer to convert the program into a specified assembly
> to prove the programmer is not stealing codes form others and faking to be
> his own works.


--
Ben.
 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      12-21-2011
On 2011-12-21, 88888 Dihedral <(E-Mail Removed)> wrote:
> A program in C code within 20 lines should be coded in assembly
> easily for professionals in any 32 bit cpu easily.


I'm guessing you haven't used all that many 32-bit CPUs.

> Then I'll ask the programmer to convert the program into a specified assembly
> to prove the programmer is not stealing codes form others and faking to be
> his own works.


Er, why?

FWIW, I have only enough knowledge of various assembly languages to read
simple stuff in them. Can't write any, never had a need to. It's not one
of the most relevant skills these days.

-s
--
Copyright 2011, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.
 
Reply With Quote
 
Keith Thompson
Guest
Posts: n/a
 
      12-21-2011
88888 Dihedral <(E-Mail Removed)> writes:
[...]
> A program in C code within 20 lines should be coded in assembly easily
> for professionals in any 32 bit cpu easily.


But why on Earth would anyone want to waste the time doing so?

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
 
Reply With Quote
 
Kenny McCormack
Guest
Posts: n/a
 
      12-21-2011
In article <(E-Mail Removed)>,
Keith Thompson <(E-Mail Removed)> wrote:
>88888 Dihedral <(E-Mail Removed)> writes:
>[...]
>> A program in C code within 20 lines should be coded in assembly easily
>> for professionals in any 32 bit cpu easily.

>
>But why on Earth would anyone want to waste the time doing so?


Why do you waste your time spewing your venom (posting) here?

Really, it's the same question - same basic answer. The answer is: Because
it makes you feel good and you have the time to waste.

As do I.

--
They say compassion is a virtue, but I don't have the time!

- David Byrne -

 
Reply With Quote
 
hopcode
Guest
Posts: n/a
 
      12-24-2011
Il 24.12.2011 16:37, io_x ha scritto:
> "io_x"<(E-Mail Removed)> ha scritto nel messaggio
> news:4ef5661d$0$1375$(E-Mail Removed). ..
>
> Buon Natale e
> Felice 2012
>


Frohe Weihnachten und
glckliches neues 2012

Cheers,

--
..:mrk[hopcode]
.64lab:.
group http://groups.google.com/group/x64lab
site http://sites.google.com/site/x64lab
 
Reply With Quote
 
Nathan
Guest
Posts: n/a
 
      12-24-2011
On Dec 24, 1:11*pm, hopcode <(E-Mail Removed)> wrote:
> Il 24.12.2011 16:37, io_x ha scritto:
>
> > "io_x"<(E-Mail Removed)> *ha scritto nel messaggio
> >news:4ef5661d$0$1375$(E-Mail Removed) ...

>
> > Buon Natale e
> > Felice 2012

>
> Frohe Weihnachten und
> glckliches neues 2012
>


Wishing a very Merry Christmas to all and have a Happy New Year!

Nathan.
 
Reply With Quote
 
88888 Dihedral
Guest
Posts: n/a
 
      12-27-2011
Keith Thompson於 2011年12月22日星期四UTC+8上午5時37分25 寫道:
> 88888 Dihedral <(E-Mail Removed)> writes:
> [...]
> > A program in C code within 20 lines should be coded in assembly easily
> > for professionals in any 32 bit cpu easily.

>
> But why on Earth would anyone want to waste the time doing so?
>
> --
> Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
> Will write code for food.
> "We must do something. This is something. Therefore, we must do this."
> -- Antony Jay and Jonathan Lynn, "Yes Minister"


I love those jobs that ordinary low paid programmers can't do
that is how I got paid well. It is not the language used but just
the difficulties and talents required to complete tough tasks
to get the rewards must be rare.
 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      12-27-2011
On 2011-12-27, 88888 Dihedral <(E-Mail Removed)> wrote:
> I love those jobs that ordinary low paid programmers can't do
> that is how I got paid well.


If your code and writing is any indication, this is a terrifying concept.

> It is not the language used but just
> the difficulties and talents required to complete tough tasks
> to get the rewards must be rare.


Huh. I would much rather put the hard work into building a robust and
maintainable design such that the skills needed to keep it running aren't
rare.

The goal here is not to show off, it's to do the best work possible.
Maintainable code is better than flashy code.

-s
--
Copyright 2011, all wrongs reversed. Peter Seebach / (E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
I am not speaking for my employer, although they do rent some of my opinions.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
problem in running a basic code in python 3.3.0 that includes HTML file Satabdi Mukherjee Python 1 04-04-2013 07:48 PM
Re: A binary search algorithm that searches for an element similar to the key Ben Bacarisse C Programming 8 12-22-2011 07:24 PM
Binary tree search vs Binary search Bogdan C Programming 22 10-21-2010 09:46 PM
Does ModelSim or any simulator software have a function similar tothe standard function any logic analizer has? Weng Tianxiang VHDL 7 09-11-2009 04:47 PM
Key generation algorithm and Cipher algorithm Ahmed Moustafa Java 0 11-15-2003 06:35 AM



Advertisments