Binary search & boundary cases

Understand the concept

Binary search works on sorted data. Compare the middle element with the target, then discard the half that cannot contain it. Repeating this reduces the number of candidate positions by about half each step.

Here, low and high are inclusive bounds. While low <= high, the target—if present—is within that interval. Setting low = middle + 1 or high = middle - 1 excludes a checked position and guarantees progress. Returning -1 signals that no match was found.

For an indexable sequence, search takes O(log n) comparisons and O(1) extra space in this iterative version. Sorting unsorted data first has a separate cost. With repeated values this algorithm returns some matching index, not necessarily the first. Test empty inputs, endpoints, absent targets, and duplicates.

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

print(binary_search([2, 5, 8, 12, 19], 12))
print(binary_search([], 12))

Output / what to expect

3
-1

Try it yourself

Test the first and last elements and a missing target. Can you call this function directly on [8, 2, 5]? Explain.

assert binary_search([2, 5, 8], 2) == 0
assert binary_search([2, 5, 8], 8) == 2
assert binary_search([2, 5, 8], 6) == -1
# [8, 2, 5] is unsorted: the algorithm's assumption is broken.
# Sort first if appropriate, noting that indices then refer to the sorted list.

Concept samjho

Binary search sorted data par kaam karta hai. Middle element ko target se compare karo, phir woh half hatao jahan target nahi ho sakta. Har step candidate positions ko lagbhag aadha karta hai.

Yahan low aur high inclusive bounds hain. Jab tak low <= high hai, target agar present hai toh isi interval mein hai. low = middle + 1 ya high = middle - 1 checked position ko hataata hai aur progress ensure karta hai. -1 ka matlab match nahi mila.

Indexable sequence ke liye search O(log n) comparisons leta hai aur iterative version mein extra space O(1) hai. Unsorted data ko sort karne ki cost alag hai. Duplicate values hon toh algorithm koi matching index deta hai, zaroori nahi first ho. Empty input, endpoints, absent target aur duplicates test karo.

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

print(binary_search([2, 5, 8, 12, 19], 12))
print(binary_search([], 12))

Output / kya expect karein

3
-1

Ab khud try karo

First aur last elements, aur missing target test karo. Kya [8, 2, 5] par directly function call karna sahi hai? Explain karo.

assert binary_search([2, 5, 8], 2) == 0
assert binary_search([2, 5, 8], 8) == 2
assert binary_search([2, 5, 8], 6) == -1
# [8, 2, 5] is unsorted: the algorithm's assumption is broken.
# Sort first if appropriate, noting that indices then refer to the sorted list.