Page History

...

Who's "right"?   That depends on where you stand and what's important to you.    Perhaps neither.   You choose what's right for what you're trying to do at that moment.   There is no gospel, only defensible but non-absolute positions.

===================================================================================================================

Binary Search in a Sorted Array

The recursive technique used to find a value in a sorted array is very useful in many situations. 

Consider the following sorted array of values:

{{\[1, 2, 4, 7, 10, 11, 12, 13, 20, 25, 27, 28, 30\]}}

Supposed you're give a value, x, what's the fastest way to either find that value in the array or determine if it is not present?

The trick is to use the same technique many people use to find a name in a phonebook, a technique called a "binary search" because it is continually making the searched space smaller by a factor of two:   

1. Open the book in the middle  mid = (max-min)/2
2. If the name you want is on that page, you're done.
3. If the name is before the names where you opened the book, re-open the book halfway on the smaller side and repeat the process.
4. If the name is after the names where you opened the book, re-open the book halfway on the larger side and repeat the process.

For the above array, we would look for the number 11 by doing the following:

1. min = 0, max = 13, so mid = 6 ==>  so look at the #12
2. min= 0, max = 6, and 11 < 12, so look at mid = (6+0)/2 = 3, i.e. the #7.
3. min= 3, max = 6, and 11 > 7, so look at the mid = (6+3)/2 = 4, i.e. the #10
4. min = 4, max = 6 and 11>10 so look at the mid=(4+6)/2 = 5, i.e. the #11
5. min = 5, max = 6,  there's only one element left and since 11 = 11, we found it! 

 Here's some Java code to do the same:

/**
 * Uses binary search to find x in the given array within the given min (inclusive) and max (exclusive) bounds.
 * returns true if found, false otherwise.
 */
boolean find(int x, int[] anArray, int min, int max) {
  if(0 >= (max-min) {
    return false;   // safety catch, should never hit this.
  }
  else if(1 == (man-min)) {   // only one element to look at
    return anArray[min] == x;   // return true is equal, false otherwise
  }
  else {   // still looking
    int mid = (max+min)/2;  // integer arithmetic will round down.
    if(anArray[mid] <= x) {  // careful here, need to make sure midpoint is included if x = anArray[mid]
       return find(x, anArray, mid, max);  // recur with smaller bounds = upper half of the original bounds.
    }
    else {
       return find(x, anArray, min, mid);  // recur with smaller bounds = lower half of the original bounds
    }
  }
}

Such as search is very fast, running in O(log N) time because you are reducing the size of the space by a constant multiplicative factor every time your recurse.

One way to look at what is going on here is to think of the sorted array as already being in the form of a binary search tree, where each mid-point is the top node of a sub-tree.    All the above algorithm is doing is walking down from the top of the binary search tree.

===================================================================================================================

Insertion into a Double-linked List