Linear, Binary and Binary-Tree Search

Linear search checks items in sequence until a match is found or the candidates are exhausted. It works without a sorting assumption. A successful first-item search takes one comparison, while the worst case requires inspecting all n items, giving O(n) time.

Specify whether the task needs the first match, every match or just a Boolean result. Duplicates change those requirements. A not-found result must be distinguishable from a valid index; a sentinel such as -1 should not be mistaken for an ordinary final array position.

Binary search requires data sorted under the comparison rule. Maintain a candidate interval, compare its midpoint and discard the half that cannot contain the target. For inclusive low/high indices, one convention uses mid=(low+high)//2, then high=mid-1 or low=mid+1.

The search ends when a match occurs or low>high. Updating a boundary to mid rather than beyond it can fail to shrink a one-item interval. O(log n) comparisons follow repeated halving, although preparing unsorted data or accessing the midpoint may add costs outside this simple indexed-array model.

Binary search in an array and search in a BST use related ordering reasoning but different storage. At a BST node, compare its key and follow the appropriate child. An absent child proves failure on that path if the ordering invariant holds.

Balanced-tree height gives O(log n) search, while an ordinary skewed tree can require O(n). Choosing a method involves update frequency, sorting cost and representation as well as a headline complexity. Trace the actual structure and target supplied before making a general performance statement.

def binary_search(values, target):
    low, high = 0, len(values) - 1
    while low <= high:
        mid = (low + high) // 2
        if values[mid] == target:
            return mid
        if values[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

print(binary_search([3, 8, 12, 19, 23, 31, 42], 23))

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.