binary search in java

Binary Search is the fast way to search a sorted array. The idea is to look at the element in the middle. If the key is equal to that, the search is finished. If the key is less than the middle element, do a binary search on the first half. If it's greater, do a binary search of the second half.

public class BinarySearch {
  private long[] a;

  private int nElems;

  public BinarySearch(int max) {
    a = new long[max]; // create array
    nElems = 0;
  }

  public int size() {
    return nElems;
  }

  public int find(long searchKey) {
    return recFind(searchKey, 0, nElems - 1);
  }

  private int recFind(long searchKey, int lowerBound, int upperBound) {
    int curIn;

    curIn = (lowerBound + upperBound) / 2;
    if (a[curIn] == searchKey)
      return curIn; // found it
    else if (lowerBound > upperBound)
      return nElems; // can't find it
    else // divide range
    {
      if (a[curIn] < searchKey) // in upper half
        return recFind(searchKey, curIn + 1, upperBound);
      else
        // in lower half
        return recFind(searchKey, lowerBound, curIn - 1);
    }
  }

  public void insert(long value) {
    int j;
    for (j = 0; j < nElems; j++)
      // find where it goes
      if (a[j] > value) // (linear search)
        break;
    for (int k = nElems; k > j; k--)
      // move bigger ones up
      a[k] = a[k - 1];
    a[j] = value; // insert it
    nElems++; // increment size
  }

  public void display() {
    for (int j = 0; j < nElems; j++)
      System.out.print(a[j] + " ");
    System.out.println("");
  }
  public static void main(String[] args) {
    int maxSize = 100;
    BinarySearch arr = new BinarySearch(maxSize);

    arr.insert(12);
    arr.insert(20);
    arr.insert(35);
    arr.insert(426);
    arr.insert(54);
    arr.insert(69);
    arr.insert(744);
    arr.insert(87);
    arr.insert(895);
    arr.insert(89);
    arr.insert(8);
    arr.insert(208);

    arr.display(); // display array

    int searchKey = 12; // search for item
    if (arr.find(searchKey) != arr.size())
      System.out.println("Found " + searchKey);
    else
      System.out.println("Can't find " + searchKey);
  }
} 

The advantage of a binary search over a linear search is astounding for large numbers. For an array of a million elements, binary search, O(log N), will find the target element with a worst case of only 20 comparisons. Linear search, O(N), on average will take 500,000 comparisons to find the element.
This performance comes at a price - the array must be sorted first. Because sorting isn't a fast operation, O(N log N), it may not be worth the effort to sort when there are only a few searches.
Output will be:

First I have used searchKey = 4
That was not in array. So it has given result Can't finf 4
Next Change value searchKey = 12
It will give you the result Found 12