0

The following SO url provides some good real-world examples for Big O notation:

What does O(log n) mean exactly?

I'm specifically interested in the following example provided for a binary search:

"O(log n): Given a person's name, find the phone number by picking a random point about halfway through the part of the book you haven't searched yet, then checking to see whether the person's name is at that point. Then repeat the process about halfway through the part of the book where the person's name lies. (This is a binary search for a person's name.)"

There are a few things about this that I'm unclear about:

  • Does a textbook binary search start by searching at the exact halfway point of an array? If there is an even number of items in the array, should a textbook binary search algorithm pick the lower or higher item at random?

  • Does a textbook binary search do a halfway search on specific data points or does it search on clustered groups of datapoints for better efficiency? Or does a binary search pattern support either one of these approaches?

  • Can binary search be applied to either sorted or unsorted arrays? Or is it always recommended to programmatically sort an array before executing a binary search?

Community
  • 1
  • 1
Jim Thompson
  • 75
  • 5

1 Answers1

0

There are certain things that the example doesn't explain properly. First, imagine that it's a dictionary in which you're searching for a name. Let's say you're searching for "John". The (n/2)th page gives you names starting with letter L (say page X). So, you ignore everything starting from this page and further since you know that this page and the further ones can't have what you're searching for. Now, your search set is reduced to searching from page 1 to page X. Keep doing the same step where you ignore n/2 items of the search set every time you select a page.

So, from the explanation I'd given:

1.) If n is even/odd, just pick what you get by n/2. You're either going to consider page 1 to (n/2)-1 (or) page (n/2)+1 to n in the next iteration. So, there's no risk of skipping any element here.

2.) At every iteration, you consider the entire search set. The difference between search sets from iteration i to i+1 is that, the number of elements will have reduced by half.

3.) One of the pre-requisites for BS is we should be considering a sorted list of items. That's the reason I've used a dictionary in my explanation.

And the reason why this operation is O(logn) is because you reduce the list of items by half every time. Imagine you've 32 items in the list. The number of iterations required to find the answer here is 5 (32 reduced to 16 in first iteration, 16 reduced to 8 in second iteration etc.). As you can see, the relationship between 32 and 5 is log 32 (base 2) = 5

attaboy182
  • 2,039
  • 3
  • 22
  • 28
  • Is there any issue with using the following routine to identify the start index?: var startIndex = Math.Round(itemCount/2); – Jim Thompson May 31 '16 at 20:31
  • If itemCount is an integer (and it should should since it's going to be an index), you should not have to worry about rounding off numbers. – attaboy182 May 31 '16 at 20:32
  • But if my set has 5 items then the following startIndex routine will return 2.5: var startIndex = Math.Round(itemCount/2); I can't access the collection with an index of 2.5 so Math.Round seems like it covers both scenarios of even or odd number of items. Wouldn't Math.Round be the better choice here? Can you write out the routine that you typically use to identify startIndex? – Jim Thompson May 31 '16 at 20:39
  • try this: int itemCount = 5; int x = (itemCount/2); Print out the value of x and see what you get. This will make things clearer for you. – attaboy182 May 31 '16 at 20:41
  • If we search all items from the middle index and higher, then (if item not found) we search all items below the middle index then we will find the item in 1-2 search calls. I was under the impression that the binary search pattern involved some type of recursive set division that would successively divide the remaining sets to search. Is the binary search pattern really as simple as just splitting a set and then performing 1-2 searches? – Jim Thompson May 31 '16 at 20:54
  • Or does the binary search work like this? Given a set of 20 items: 1. Search from item 11-20 2. Item not found 3. Search from item 5-10 4. Item not found 5. Search from item 3-4 6. Item not found 7. Search from item 1-2 8. Match found in item 1 9. Return 1 – Jim Thompson May 31 '16 at 21:01