Efficiently Finding Elements: Implementing Binary Search

Binary search is a fundamental algorithm for efficiently locating a target value within a sorted list. It repeatedly divides the search interval in half, significantly reducing the number of comparisons needed compared to a linear search, especially for large datasets. Your task is to implement a binary search function in Python.

Problem Description

You are required to implement a function called binary_search that takes a sorted list of integers (nums) and a target integer (target) as input. The function should return the index of the target within the nums list if it exists. If the target is not found, the function should return -1.

Key Requirements:

• The input list nums is guaranteed to be sorted in ascending order.
• The function must implement the binary search algorithm correctly.
• The function should handle cases where the target is at the beginning, middle, or end of the list.
• The function must correctly handle the case where the target is not present in the list.

Expected Behavior:

The function should efficiently search the sorted list and return the index of the target if found. If the target is not found, it should return -1. The algorithm should repeatedly divide the search interval in half until the target is found or the interval is empty.

Edge Cases to Consider:

• Empty input list (nums is empty).
• Target is smaller than the smallest element in the list.
• Target is larger than the largest element in the list.
• Duplicate elements in the list (the function only needs to return one valid index if the target appears multiple times).

Examples

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 is found at index 4 in the sorted list.

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 is not present in the sorted list.

Example 3:

Input: nums = [2,5], target = 5
Output: 1
Explanation: 5 is found at index 1.

Example 4:

Input: nums = [2,5], target = 1
Output: -1
Explanation: 1 is not present in the list.

Constraints

• The length of the input list nums will be between 0 and 10000 (inclusive).
• Each element in nums will be an integer.
• The target will be an integer.
• The time complexity of your solution should be O(log n), where n is the length of the input list.

Notes

• Binary search relies on the input list being sorted. Ensure your function does not attempt to sort the list.
• Consider using a while loop to repeatedly narrow down the search interval.
• Keep track of the low and high indices to define the current search interval.
• In each iteration, calculate the mid index and compare the element at nums[mid] with the target.
• Adjust the low or high index based on the comparison result to narrow the search interval.