The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.
|
 |
|
Dev Shed Forums
> Programming Languages - More
> Software Design
|
Binairie searching
Discuss Binairie searching in the Software Design forum on Dev Shed. Binairie searching Software design forum discussing design principles and non-language specific algorithms. Get help with logic, algebraic, or relational concepts.
|
|
 |
|
|
|
|

Dev Shed Forums Sponsor:
|
|
|

April 30th, 2003, 06:47 AM
|
|
Registered User
|
|
Join Date: Apr 2003
Location: The Netherlands, near Amsterdam
Posts: 3
Time spent in forums: 3 m 2 sec
Reputation Power: 0
|
|
|
Binary tree
Sorry for if my English is a bit poor
This technique is very usefull if you need to find a value in a very large array. It works much and much faster then looping through your array waiting to find your value.
This is how it works:
You check the value in the middle of your array. You check if this value is smaller or larger then the value you are looking for. If it's smaller you take the left part of the array, if it's bigger you take the right part of the array. You keep on doing this until you find your value.
Note that your array needs to be sorted to use this technique.
Below is an example of a Java-applet that I wrote:
Code:
import java.awt.*;
import java.applet.*;
import java.awt.event.*;
import java.util.*;
public class BinSearching extends Applet
{
int reeks[];
Button random,zoek;
TextField zoekgetal;
boolean nieuweReeks,gevonden,einde;
public void init()
{
reeks = new int[10];
random = new Button("Getallen");
random.addActionListener(new GetallenHandler());
zoek = new Button("Zoek");
zoek.addActionListener(new GetallenHandler());
zoekgetal = new TextField(10);
nieuweReeks = false;
gevonden = false;
einde = false;
add(random);
add(zoekgetal);
add(zoek);
}
public void paint(Graphics g)
{
int x = 20;
if(nieuweReeks) {
for(int i = 0; i < reeks.length; i++) {
g.drawString("" + reeks[i],x,50);
x += 25;
}
nieuweReeks = false;
}
if(gevonden) {
g.drawString("Gevonden!",100,100);
}
if(einde) {
g.drawString("Niet Gevonden!",100,100);
}
}
class GetallenHandler implements ActionListener
{
public void actionPerformed(ActionEvent e)
{
if(e.getSource() == random) {
for(int i = 0; i < reeks.length; i++) {
reeks[i] = (int) (100 * Math.random() + 1);
}
Arrays.sort(reeks);
nieuweReeks = true;
repaint();
}
if(e.getSource() == zoek) {
int getal = Integer.parseInt(zoekgetal.getText());
int onder = 0;
int boven = reeks.length - 1;
int midden = (onder + boven) / 2;
while(!gevonden && !einde) {
if(getal == reeks[midden]) {
gevonden = true;
repaint();
break;
}
if(getal < reeks[midden]) {
boven = midden - 1;
}
if(getal > reeks[midden]) {
onder = midden + 1;
}
if(onder > boven) {
einde = true;
repaint();
break;
}
else {
midden = (onder + boven) / 2;
}
}
}
}
}
}
Last edited by CrazyLegz : April 30th, 2003 at 03:59 PM.
|

April 30th, 2003, 12:15 PM
|
|
Contributing User
|
|
Join Date: Oct 2000
Location: Back in the real world.
|
|
Quote: | Note that your array needs to be sorted to use this technique. |
"Binary Tree" is the name, commonly used with linked lists...
When posting algorithms, you should not use variables or functions with names from your language. Itīs very hard to read for someone not knowing dutch. Better use english everywhere here.
|

April 30th, 2003, 03:53 PM
|
|
Registered User
|
|
Join Date: Apr 2003
Location: The Netherlands, near Amsterdam
Posts: 3
Time spent in forums: 3 m 2 sec
Reputation Power: 0
|
|
Quote: | "Binary Tree" is the name, commonly used with linked lists... |
Ok.....I didn't knew the English word for it.
Quote: |
When posting algorithms, you should not use variables or functions with names from your language. Itīs very hard to read for someone not knowing dutch. Better use english everywhere here. |
You're right, sorry for that, I just copy-pasted it...
|

May 20th, 2003, 02:22 PM
|
|
Registered User
|
|
Join Date: May 2003
Posts: 10
Time spent in forums: 38 m 39 sec
Reputation Power: 0
|
|
|
The main problem with binary search is that the data already has to be sorted and it may end up being more work than just doing a linear search in alot of cases since in a linear search, the data does not have to be sorted.
So:
Time for(Quicksort+binarysearch)>time for (Linear search)
|

May 20th, 2003, 04:11 PM
|
 |
digital sinner
|
|
Join Date: Mar 2003
Location: sinner's land
Posts: 68
Time spent in forums: 4 h 37 m 30 sec
Reputation Power: 11
|
|
|
yes...but you can insert your data sorted already...so you won't have to sort it again and again.
|

May 20th, 2003, 06:41 PM
|
|
Registered User
|
|
Join Date: May 2003
Posts: 10
Time spent in forums: 38 m 39 sec
Reputation Power: 0
|
|
|
Hmm, yeah that would certainly work. I was thinking of different strings of random numbers.
|
Developer Shed Advertisers and Affiliates
| Thread Tools |
Search this Thread |
|
|
|
| Display Modes |
Rate This Thread |
Linear Mode
|
|
Posting Rules
|
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off
|
|
|
|
|