Software Design
 
Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
User Name:
Password:
Remember me

The Shed is going Social! Join us on FaceBook and Twitter and chime in on the conversation.

Go Back   Dev Shed ForumsProgramming Languages - MoreSoftware Design

Reply
Add This Thread To:
  Del.icio.us   Digg   Google   Spurl   Blink   Furl   Simpy   Y! MyWeb 
Thread Tools Search this Thread Rate Thread Display Modes
 
Unread Dev Shed Forums Sponsor:
  #1  
Old April 30th, 2003, 06:47 AM
CrazyLegz CrazyLegz is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Apr 2003
Location: The Netherlands, near Amsterdam
Posts: 3 CrazyLegz User rank is Just a Lowly Private (1 - 20 Reputation Level) 
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.

Reply With Quote
  #2  
Old April 30th, 2003, 12:15 PM
M.Hirsch M.Hirsch is offline
Contributing User
Dev Shed God 1st Plane (5500 - 5999 posts)
 
Join Date: Oct 2000
Location: Back in the real world.
Posts: 5,966 M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level)M.Hirsch User rank is First Lieutenant (10000 - 20000 Reputation Level) 
Time spent in forums: 1 Month 2 Days 52 m 24 sec
Reputation Power: 189
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.
__________________
--
Manuel Hirsch - Linux, FreeBSD, programming, administration articles, tutorials and more.

Reply With Quote
  #3  
Old April 30th, 2003, 03:53 PM
CrazyLegz CrazyLegz is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Apr 2003
Location: The Netherlands, near Amsterdam
Posts: 3 CrazyLegz User rank is Just a Lowly Private (1 - 20 Reputation Level) 
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...

Reply With Quote
  #4  
Old May 20th, 2003, 02:22 PM
Archbob Archbob is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: May 2003
Posts: 10 Archbob User rank is Just a Lowly Private (1 - 20 Reputation Level) 
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)

Reply With Quote
  #5  
Old May 20th, 2003, 04:11 PM
heinrich's Avatar
heinrich heinrich is offline
digital sinner
Dev Shed Newbie (0 - 499 posts)
 
Join Date: Mar 2003
Location: sinner's land
Posts: 68 heinrich User rank is Just a Lowly Private (1 - 20 Reputation Level) 
Time spent in forums: 4 h 37 m 30 sec
Reputation Power: 11
Send a message via Yahoo to heinrich
yes...but you can insert your data sorted already...so you won't have to sort it again and again.

Reply With Quote
  #6  
Old May 20th, 2003, 06:41 PM
Archbob Archbob is offline
Registered User
Dev Shed Newbie (0 - 499 posts)
 
Join Date: May 2003
Posts: 10 Archbob User rank is Just a Lowly Private (1 - 20 Reputation Level) 
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.

Reply With Quote
Reply

Viewing: Dev Shed ForumsProgramming Languages - MoreSoftware Design > Binairie searching

Developer Shed Advertisers and Affiliates



Thread Tools  Search this Thread 
Search this Thread:

Advanced Search
Display Modes  Rate This Thread 
Rate This Thread:


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

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
View Your Warnings | New Posts | Latest News | Latest Threads | Shoutbox
Forum Jump

Forums: » Register « |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support | 
  
 


Powered by: vBulletin Version 3.0.5
Copyright ©2000 - 2013, Jelsoft Enterprises Ltd.

© 2003-2013 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap