Sunny and the Algorithms of Gloom: Chapter 3.1

Robert hummed thoughtfully. "Well, perhaps Elsie is right."

Sunny glanced at him in surprise, but Robert continued, "You need to learn more if you're to stand a chance against any real antagonists."

Sunny nodded slowly, her gaze drifting across the plaza in front of the library. "How long will that take? And when can we get back to tracking down the robbers? They took the dark magic book…" Despite herself, Sunny couldn't help but feel a tiny bit glad the book was gone, because now she wasn't feeling nauseous at all.

"I trust that the police will easily be able to track the robbers down." Robert eyed Sunny. "Unlike in your mystery books, the police here have access to tracking-bots that can find those books. All we need to do is keep an eye on the news. That means you can train for a few days… and I know just the place."

* * *

When Robert had mentioned training, Sunny had visualized an ancient temple with warrior monks ready to teach her secret martial arts techniques. Or, y'know, coding techniques. Or if not a temple, at the very least, Robert could've taken her to a magical clearing in the woods, or a mountain top…

But instead, Sunny got to go to an office building.

She tipped her head back, tracing the blue windows of the building up to its not-particularly-impressive height of three stories. Javalandians strolled in and out of the revolving doors, and a neat line of trees decorated the pavement in front of the building.

"Robert, are you sure this is the place?" Sunny glanced at Robert skeptically as she finished the semicolon sandwich she'd bought for lunch. (Well, Robert had bought it for her. Unfortunately, being a hero didn't come with a salary.)

The robot ambassador floated forwards. "Yes, I am. Come along now."

Sunny shrugged and followed him through the revolving doors.

Inside, Sunny saw the most robots she'd ever seen in one place before. They were floating around desks and cubicles, carrying batteries and books and boxes. Some were decorated in brightly-colored zigzags or stripes. One was watering a potted plant to the side while chatting with another robot.

Sunny spotted a few humans sitting at desks in one corner, but for the most part, there were only robots. Down a hallway to the right, an elevator dinged, and more robots came hovering out.

"What did you say this place was, again?" Sunny whispered to Robert.

"The Method City branch of the Javalandian Ambassadors!" he declared proudly. Robert led Sunny to the right, towards the elevator.

Sunny ducked around a robot carrying a large stack of folders. "So these are all ambassadors like you?"

"Indeed. Although I specialize in Javaland to Earth communications, while most of these ambassadors deal with relations to foreign nations or internal matters." A couple of robots waved to Robert, and he waved back.

Robert stopped right before the elevators and waved an arm slab at a slate gray door to the left. A small green light blinked on, and then the door slid to the side.

Sunny followed Robert into the room. "So by internal matters, what exactly-" She caught sight of the main feature of the room and stopped short. "Is that… a TV?" For some reason, she hadn't expected to see a TV here. Although perhaps it should've been expected, considering Javaland had technology like robots and elevators.

"Indeed. This is our training room for non-robot employees." Robert gestured towards the desk in the center, and Sunny took a seat. "We're being quite considerate here, allowing you all enough time and resources to learn what ambassadors can download in seconds."

"Oh-kay. No need to flaunt your downloading skills." Sunny laughed, then noticed a pen and paper in front of her and glanced at Robert questioningly.

"For notes," he said. "It's a good idea to jot down the values of variables as you walk through code. For example, with binary search, you'll want to keep track of left, right, and mid."

Sunny blinked. "What search?"

"Never mind. Let's just start the video."

Robert settled onto the other seat as the TV flickered on.

A pleasant voice welcomed Sunny and Robert as a list of numbers appeared on the screen.

4 2 5 1 3

"Here we have an array of numbers," it said. "Right now, it's not sorted. So, if we were to search for the value of 5, we would have to go one by one until we either found the value or reached the end of the array."

A green arrow pointed to the first element, 4, then moved to the right until it hit 5.

"In this case, we found the value at index two."

The screen waited a moment, then expanded to show a list of a hundred numbers arrayed in a grid, with the number 5 in the bottom right corner.

"But what if we had a longer unsorted array? It would take a while to find the value. We need something more efficient."

The words "Binary Search" appeared in large block letters and a smiley-face popped up to the side. Sunny briefly wondered if they used this same video to teach elementary schoolers.

"The answer: binary search! Binary search works by halving the area to search in each time. This makes it very efficient. Now, the first step is to sort the array."

The screen displayed the same array as in the first example, except sorted.

1 2 3 4 5

"Then, define two variables to represent the first and last indices. In this case, we'll call them l for left and r for right, and initialize them to 0 and 5."

int l = 0;

int r = 5;

"We also need a variable to represent the midpoint index. We'll call that mid. Remember, binary search works by narrowing down the search area. That could mean narrowing it down to the range of left to mid, or mid to right."

int mid;

"Next, we need a while loop, so we can keep searching until we find the element or determine that it's not in the array. We can tell if it's not in the array if the left and right variables point to the same index. That means we've searched and narrowed down the search area until it's less than an element."

while (l < r) {

}

"Inside this while loop, we'll update mid, then do different things based on whether the value at index mid is less than, equal to, or greater than the value we're searching for."

while (l < r) {

    mid = (l + r) / 2;

    if (arr[mid] < val) {

    } else if (arr[mid] == val) {

    } else {

    }

}

"If the value at mid is less than the target value, we know that the target value must be in the right half. Likewise, if the value at mid is greater than the target value, we know it must be in the left half. If the value at mid is the target value, we can return mid, because that's the index we found the target value at. This is assuming we're in a binary search method, and returning will make us exit the method immediately."

while (l < r) {

    mid = (l + r) / 2;

    if (arr[mid] < val) {

        l = mid+1;

    } else if (arr[mid] == val) {

        return mid;

    } else {

        r = mid;

    }

}

"If the loop ends without us returning mid, that means we haven't found the element. So, we can return -1. Here is the completed code."

public static int binSearch(int val) {

    int l = 0;

    int r = arr.length;

    int mid;

    while (l < r) {

        mid = (l + r) / 2;

        if (arr[mid] < val) {

            l = mid+1;

        } else if (arr[mid] == val) {

            return mid;

        } else {

            r = mid;

        }

    }

    return -1;

}

The screen faded to black, and Robert turned to look at Sunny expectantly. "So. What'd you think?"

Sunny blinked back at him. "I, uh. I think I would very much like some downloading skills."