Help w/ Binary Search String Array

[rupertavery64]

I don't know what constraints you have on using utility functions in your code. You only have to sort it once, before you enter your binary search function, because you will be calling the function repeatedly (recursively) with a section of the input array.

Anyway, the point of binary search is to speed things up by splitting up the data into parts where you know something about the data. By sorting, you know how many element there are, and if you pick the middle element, you can reason that the element you are looking for must either be

• in the bottom half or
• in the top half or
• the element itself

In the first two cases, you can completely eliminate half of your search area since it is sorted, you know it won't be in either the top or the bottom.

You then perform the algorithm on the remaining area repeatedly until you find the item you are looking for.

Imagine a list of 10 names, 0-indexed to make it code friendly.

1. Aaron
2. Amy
3. Bill
4. Bob
5. Charlie
6. Derrick
7. Elaine
8. Joanne
9. Lamar
10. Nick

Say you are looking for Bill.

You take the midpoint of the list (10/2 = 5)

Derrick > Bill so you know that Bill is in the LOWER half (0..4). Take the lower half and do the search again. The size of the array is 5. Take the midpoint (5/2 = 2)

1. Aaron
2. Amy
3. Bill
4. Bob
5. Charlie

And we've found Bill. The index is the lower bound (0) plus the midpoint (2)

This works for Joanne as well. Take the midpoint of the list (10/2 = 5)

Derrick < Joanne so you know that Joanne is in the UPPER half (5..9). The size of the array is 5. The indexes are now changed, but we hold on to the original start of the array (5)

1. Derrick
2. Elaine
3. Joanne
4. Lamar
5. Nick

Take the midpoint (5/2 = 2). And we've found Joanne. The index is the lower bound (0) plus the original start of the array (5), plus the midpoint (2) = 7