CS1021C Quiz 9 Key - Binary Search

Flashcards covering key concepts related to binary search and recursive functions in programming.

Binary Search

An efficient algorithm for finding an item from a sorted list of items, by repeatedly dividing the search interval in half.

Recursive Function

A function that calls itself to solve smaller instances of the same problem, commonly used in binary search.

Midpoint Calculation

In binary search, the midpoint is calculated as mid = (first + last) / 2 to determine the next point of comparison.

String Comparison

The process of comparing two strings to determine their lexicographical order.

Sorted List

A list of elements arranged in a defined order, usually ascending or descending based on some criterion.

Base Case

In recursive functions, the condition under which no further recursive calls are made; for binary search, when first > last.

Return Value

The output of a function; in this binary search function, it indicates the index of the found item or -1 if not found.

Difference (diff) in Binary Search

The result of comparing the key with the element at the midpoint: 0 for equal, negative for less, positive for greater.

First and Last Indices

Variables representing the current bounds of the search within the array; first is the starting index, last is the ending index.

Recursive Call

A call to a function within itself, enabling the function to continue working on smaller portions of the original problem.