0704. Binary Search

Problem

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

Examples

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

Constraints:

1 <= nums.length <= 104
-104 < nums[i], target < 104
All the integers in nums are unique.
nums is sorted in ascending order.

Analysis

Solution

def solution(nums, target, l, r) -> int:
    l, r = 0, len(nums)-1
    m = _binary(nums, l, r, target)

    return m
def _binary(nums, l, r, target):
    if r - l <= 1:
        if nums[l] == target:
            return l
        elif nums[r] == target:
            return r
        else:
            return -1
    
    m = int((r-l)/2)+l
            
    if nums[m] > target:
        l = l
        r = m-1
        return _binary(nums, l, r, target)
        
    elif nums[m] < target:
        l = m+1
        r = r
        return _binary(nums, l, r, target)
    else:
        return m

# test
nums = [-1,0,3,5,9,12]
target = 9
print(solution(nums, target, 0, len(nums)-1))

nums = [-1,0,3,5,9,12]
target = 2
print(solution(nums, target, 0, len(nums)-1))

nums = [-1, 0]
target = -1
print(solution(nums, target, 0, len(nums)-1))

4
-1
0

def solution(nums, target) -> int:
    
    n = len(nums)
    l, r = 0, n-1
    m = int((r-l)/2)
    
    while r > 1+l:
        if nums[m] == target:
            return m
        
        if nums[m] > target:
            # move left
            r = m
            m = int((r-l)/2) + l
        
        if nums[m] < target:
            # move right
            l = m
            m = int((r-l)/2) + l
            
    if r <= l + 1:
        if nums[l] == target:
            return l
        elif nums[r] == target:
            return r
        else:
            return -1

# test
nums = [-1,0,3,5,9,12]
target = 9
print(solution(nums, target))

nums = [-1,0,3,5,9,12]
target = 2
print(solution(nums, target))

nums = [-1, 0]
target = -1
print(solution(nums, target))        

4
-1
0

def binary(nums, l, r, target):
    if r >= l:
        m = int((r - l)/2) + l
        
        if nums[m] == target:
            return m
        elif nums[m] > target:
            return binary(nums, l, m-1, target) 
        else:
            return binary(nums, m+1, r, target)
    else:
        return -1

# test
nums = [-1, 0, 3, 5, 9, 12]
target = 9
print(binary(nums, 0, len(nums)-1, target))

nums = [-1,0,3,5,9,12]
target = 2
print(binary(nums, 0, len(nums)-1, target))

nums = [-1, 0]
target = -1
print(binary(nums, 0, len(nums)-1, target))

4
-1
0