title: Binary search in Java - learning it "my way"
body: <p>So I'm trying to teach myself how to implement a binary search in Java, as the topic might have given away, but am having some trouble.</p>
  
  <p>See, I tend to be a little stubborn, and I'd rather not just copy some implementation off the internet.</p>
  
  <p>In order to teach myself this, I created a very (VERY) rough little class which looks as follows:</p>
  
  <pre><code>public class bSearch{
  
  /**
   * @param args
   */
  
  public static void main(String[] args) {
  
      int one = 1;
      int two = 2;
      int three = 3;
      int four = 4;
      int five = 5;
      int six = 6;
  
      ArrayList tab = new ArrayList();
  
      tab.add(one);
      tab.add(two);
      tab.add(three);
      tab.add(four);
      tab.add(five);
      tab.add(six);
  
      System.out.println(bSearch(tab, 53));
  
  }
  
  @SuppressWarnings({ "rawtypes", "unchecked" })
  public static int bSearch(ArrayList tab, int key) {
  
      if (tab.size() == 0)
          return 0;
  
      if ((int) tab.get(tab.size() / 2) == key)
          return key;
  
      ArrayList smallerThanKey = new ArrayList();
      ArrayList largerThanKey = new ArrayList();
  
      for (int i = 0; i &lt; (tab.size() + 1) / 2; i++) {
          smallerThanKey.add(tab.get(i));
      }
  
      System.out.println("Smaller array = " + smallerThanKey);
  
      for (int i = (tab.size() + 1) / 2; i &lt; tab.size(); i++) {
          largerThanKey.add(tab.get(i));
      }
  
      System.out.println("Larger array = " + largerThanKey);
  
      if (key &lt; (int) tab.get(tab.size() / 2)) {
          bSearch(smallerThanKey, key);
      } else {
          bSearch(largerThanKey, key);
      }
  
      return key;
      }
  }
  </code></pre>
  
  <p>As you can see, it's pretty far from beautiful, but it's clear enough for a noobie like myself to understand, anyway.</p>
  
  <p>Now, here's the problem; when I feed it a number that is in the <code>ArrayList</code>, it feeds the number back to me (hurray!), but when I feed it a number that's not in the <code>ArrayList</code>, it still feeds me my number back to me (boo!).</p>
  
  <p>I have a feeling my error is very minor, but I just can't see it.</p>
  
  <p>Or am I all wrong, and there is some larger fundamental error?</p>
  
  <p>Your help is deeply appreciated!</p>
  
  <p><strong><em>UPDATE</em></strong></p>
  
  <p>Thanks for all the constructive comments and answers! Many helpful pointer in the right direction by several of you. +1 for everyone who bumped me along the right path.</p>
  
  <p>By following the advice you gave, mostly relating to my recursions not ending properly, I added a few <code>return</code> statements, as follows;</p>
  
  <pre><code>if (key &lt; (int) tab.get(tab.size() / 2)) {
       return bSearch(smallerThanKey, key);
  } else {
       return bSearch(largerThanKey, key);
  }
  </code></pre>
  
  <p>Now, what this does is one step closer to what I want to achieve.</p>
  
  <p>I now get <code>0</code> if the number is nowhere to be found, and the number itself if it <em>is</em> to be found. Thus progress is being made!</p>
  
  <p>However, it does not work if I have it search for a negative number or zero (not that I know why I should, but just throwing that out there).</p>
  
  <p>Is there a fix for this, or am I barking up the wrong tree in questioning?</p>