704. Binary Search

Easy

Problem:

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

https://leetcode.com/problems/binary-search/

What to know:

Binary Search Algorithm Bug

mid = (left + right) // 2

If the sum of left and right exceeds the maximum value of the data type, unexpected results can occur in C. For example, if the sum surpasses $2^{31} -1$ for an int type, Java will throw an error. This happens because the result exceeds the maximum value that the int data type can hold, causing an overflow.

To avoid this overflow, one can compute the mid value using left + (right - left) / 2:

• The value of (right - left) is always smaller than right, hence there is no risk of overflow.

• Adding left to (right - left) / 2 will not exceed right, so there is also no risk of overflow in this case.

Bisect Algorithm

The purpose of Bisect algorithm is to find a position in list where an element needs to be inserted to keep the list sorted.

Python in its definition provides the bisect algorithms using the module “bisect” which allows keeping the list in sorted order after the insertion of each element.

The bisect_left() method is provided by the bisect module, which returns the left-most index to insert the given element, while maintaining the sorted order.

import bisect

bisect.bisect_left(list, element)

1. list: This contains a list of sorted integers.

2. element: This provides an element that needs to be inserted into the sorted list.

---

Reference:

• https://www.geeksforgeeks.org/bisect-algorithm-functions-in-python/

• https://www.educative.io/answers/what-is-bisectbisectleft-in-python

Solution:

Recursion

On coding test platforms, Python has a limit on the number of recursive calls. Therefore, any recursive solution should ideally be implemented to solve within 1,000 iterations.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        def binary_search(left, right):
            if left <= right:
                # Binary Search Algorithm Bug fixed
                mid = left + (right - left) // 2

                if nums[mid] < target:
                    return binary_search(mid + 1, right)
                elif nums[mid] > target:
                    return binary_search(left, mid - 1)
                else:
                    return mid
            else:
                return -1
        
        return binary_search(0, len(nums) - 1)

Iteration

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) // 2

            if nums[mid] < target:
                left = mid + 1
            elif nums[mid] > target:
                right = mid - 1
            else:
                return mid
        return -1

bisect Module

Binary search always maintains consistent speed. Binary search operates at $O(logn)$ time complexity. The reason for its near-constant search speed, regardless of the input size, is due to the logarithmic nature. Therefore, if the array is large and the values to be found are not always at the beginning, it's advisable to use Python's binary search module, bisect, to find the position.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        index = bisect.bisect_left(nums, target)

        if index < len(nums) and nums[index] == target:
            return index
        else:
            return -1

index() Method

The index() method raises an error if the value doesn't exist. Therefore, you should handle the ValueError exception. The index() function searches sequentially from the beginning, so in the worst case, it takes $O(n)$ time complexity. The search speed progressively slows down for values located towards the end.

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        try:
            return nums.index(target)
        except ValueError:
            return -1