The find_in_sorted function performs a binary search on a sorted list of numbers to find a target value, returning its index if found, and -1 otherwise. It uses a binary search algorithm to efficiently search through the list by repeatedly dividing the search interval in half.

Cell 3

def find_in_sorted(nums, target):
    """Binary search."""
    start, end = 0, len(nums)-1
    while start < end:
        mid = (start+end)//2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            start = mid+1
        else:
            end = mid-1
    return -1

assert find_in_sorted([], 0) == -1
assert find_in_sorted([1,2,3], 0) == -1
assert find_in_sorted([1,2,3], 2) == 1
assert find_in_sorted([1,2,2,2,2,2,3], 2) in range(1, 6)
assert find_in_sorted([1,2,3,4,6,7,8,12,13,16], 12) == 7
print('All passed!')

python
def find_in_sorted(nums, target):
    """
    Binary search in a sorted list.

    Args:
    - nums (list): A sorted list of numbers.
    - target: The target number to be searched.

    Returns:
    - int: The index of the target number if found, otherwise -1.
    """
    
    # Check if the input list is empty
    if not nums:
        return -1  # or raise an exception, depending on the desired behavior

    # Initialize the search range
    left, right = 0, len(nums) - 1

    # Perform binary search
    while left <= right:
        mid = (left + right) // 2  # Use bitwise shift for more efficiency
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Test cases
assert find_in_sorted([], 0) == -1
assert find_in_sorted([1, 2, 3], 0) == -1
assert find_in_sorted([1, 2, 3], 2) == 1
assert find_in_sorted([1, 2, 2, 2, 2, 2, 3], 2) in range(1, 6)
assert find_in_sorted([1, 2, 3, 4, 6, 7, 8, 12, 13, 16], 12) == 7

print('All passed!')

Binary Search Function

find_in_sorted Function

Description

The find_in_sorted function performs a binary search on a sorted list of numbers to find a target value.

Parameters

• nums: A sorted list of numbers.
• target: The value to be searched for in the list.

Return Value

The index of the target value in the list if found, otherwise -1.

Example Use Cases

• Searching for a value in a sorted list.
• Finding the index of a value in a sorted list.

Algorithm

The function uses a binary search algorithm to find the target value in the list. It works by repeatedly dividing the search interval in half and searching for the target value in one of the two halves until it is found or the search interval is empty.

def find_in_sorted(nums, target):
    """Binary search."""
    start, end = 0, len(nums)-1
    while start < end:
        mid = (start+end)//2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            start = mid+1
        else:
            end = mid-1
    return -1