LeetCode 3: 704 - Binary Search

link to my leetcode profile

1. Problem Description

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.

1.1 Example 1:

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

1.2 Example 2:

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

3. Code

Test the cases that its larger, smaller and on the split.

3.1 larger than binary split

class Solution:
    def search(self, nums: [int], target: int) -> int:
        l = 0
        r = len(nums)

        while l<r:
            m = (l+r)//2
           # [[0],  1, {2}, 3, *4*, [5]]
           # [[-1], 0, {3}, 5, *9*, [12]] 
            if nums[m]<target: #if 3<9:
                l = m + 1
           # [[3], *4*, [5]]
           # [[5], *9*, [12]] 
            elif nums[m]>target:
                r = m
            else:
                return m
        return -1
    
arr = [-1,0,3,5,9,12]
soln = Solution()
soln.search(arr, 9)

4

3.2 less than binary split

class Solution:
    def search(self, nums: [int], target: int) -> int:
        l = 0
        r = len(nums)

        while l<r:
            m = (l+r)//2
           # [[0],1,{2},3,*4*,[5]]
           # [{-1}, 9, {10}, 11, 12, [12]] 
            
            if nums[m]<target:
                l = m + 1

           # [[0],*1*,{2},3,*4*,[5]]
           # [{-1}, *9*, {10}, 11, 12, [12]] 
                
            elif nums[m]>target:
                
           # [[0],*1*,[2],3,*4*,[5]]
           # [{-1}, *9*, [10], 11, 12, [12]]                
                r = m
            else:
                return m
        return -1

arr = [-1,9,10,11,12,12]
soln = Solution()
soln.search(arr, 9)

1

3.3 On a split

class Solution:
    def search(self, nums: [int], target: int) -> int:
        l = 0
        r = len(nums)

        while l<r:
            m = (l+r)//2
           # [[0],1,{2},3,*4*,[5]]
           # [{7}, 8, {*9*}, 11, 12, [13]] 
            
            if nums[m]<target:
                l = m + 1                
            elif nums[m]>target:          
                r = m
            else:
                return m
        return -1
    

arr = [7,7,9,11,12,13]
soln = Solution()
soln.search(arr, 9)

2

4.4 Clean version

class Solution:
    def search(self, nums: [int], target: int) -> int:
        l = 0
        r = len(nums)

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

6. Submit

Middle of the pack

Go to Main Blog
Go to LeetCode Blog