Binary search is efficient only under specific conditions: the input array must be sorted and contain unique elements. If duplicates exist, the algorithm might return any one of the matching indices rather than a guaranteed specific one.

A critical concept in binary search is the "loop invariant," which relies on a strict definition of the search interval. You must consistently maintain this interval definition throughout the loop execution.

Approach 1: Closed Interval [low, high]

When defining the search space as a closed interval, both the starting index low and the ending index high are inclusive. This leads to specific logic constraints:

• The loop condition is while low <= high. This is necessary because when low equals high, the index is still valid and must be checked.
• If the middle element is greater than the target, the new boundary high becomes mid - 1, as mid is confirmed not to be the target.

Implementation in Python:

class Solution:
    def search(self, arr: List[int], val: int) -> int:
        start = 0
        end = len(arr) - 1
        
        while start <= end:
            # Calculate mid point using floor division to avoid overflow and ensure int
            mid = start + (end - start) // 2
            
            if arr[mid] == val:
                return mid
            elif arr[mid] < val:
                start = mid + 1
            else:
                end = mid - 1
                
        return -1

Approach 2: Half-Open Enterval [low, high)

Alternatively, you can define the interval as half-open, where low is inclusive but high is exclusive. This changes the boundary logic:

• The loop condition is while low < high. If low equals high, the search space is empty.
• If the midddle element is greater than the target, the new boundary high is set to mid. Since high is exclusive, mid will not be revisited in the next itertaion.

Implementation in Python:

class Solution:
    def search(self, arr: List[int], val: int) -> int:
        start = 0
        end = len(arr)
        
        while start < end:
            mid = start + (end - start) // 2
            
            if arr[mid] == val:
                return mid
            elif arr[mid] < val:
                start = mid + 1
            else:
                end = mid
                
        return -1