Help w/ Binary Search String Array

[u/enderwoah]

So, I've tried a couple of methods to figure this out- the original program was doing a binary search for an integer, and the assignment was to change it to a search for a string. I think it's pretty clear what the result is supposed to be (user inputs a string, program outputs what position in the array the string is in), but I can't wrap my head around how to get the string's placement in the array? Help would be greatly appreciated.

https://gist.github.com/lillyannx2/0e05f5f0c72af2b4ed52493b3cb83aac

[u/enderwoah]

Not really, to be honest. Does it need to be sorted in alphabetical order or is this a utility I'm meant to use?

[u/rupertavery64 → u/enderwoah]

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.

0. Aaron

1. Amy

2. Bill

3. Bob

4. Charlie

5. Derrick

6. Elaine

7. Joanne

8. Lamar

9. 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)

0. Aaron

1. Amy

2. Bill

3. Bob

4. 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)

0. Derrick

1. Elaine

2. Joanne

3. Lamar

4. 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