#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Location
    The Netherlands, near Amsterdam
    Posts
    3
    Rep 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 04:59 PM.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Oct 2000
    Location
    Back in the real world.
    Posts
    5,966
    Rep Power
    191
    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.
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2003
    Location
    The Netherlands, near Amsterdam
    Posts
    3
    Rep Power
    0
    "Binary Tree" is the name, commonly used with linked lists...
    Ok.....I didn't knew the English word for it.

    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...
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2003
    Posts
    10
    Rep 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)
  8. #5
  9. digital sinner
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2003
    Location
    sinner's land
    Posts
    68
    Rep Power
    12
    yes...but you can insert your data sorted already...so you won't have to sort it again and again.
  10. #6
  11. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2003
    Posts
    10
    Rep Power
    0
    Hmm, yeah that would certainly work. I was thinking of different strings of random numbers.

IMN logo majestic logo threadwatch logo seochat tools logo