Modified Binary Search - Python


  • 0
    J

    The trick is to modify the binary search condition as follow:
    Let's search the half of the array where:

    1. Normal condition (target is within the sorted part):

    nums[s] < nums[mid] (the first half is sorted)

    and

    (target-nums[s]) * (target - nums[mid]) <= 0 (target is within the range)

    or

    1. the other half is sorted, but target doesn't lie within the range:

    not (

    nums[mid] < nums[e] (the second half is sorted)

    and

    (target-nums[e]) * (target - nums[mid]) > 0 ) (target is NOT within the range)


    class Solution(object):
        def search(self, nums, target):
            
            s = 0
            e = len(nums)-1
            
            while s<=e:
                mid = (s+e)/2
                
                vmid = nums[mid]
                vs = nums[s]
                ve = nums[e]
                
                if vmid == target:
                    return mid
                elif vs == target:
                    return s
                elif ve == target:
                    return e
                    
                if ((target-vs) * (target - vmid) <= 0 and vs < vmid) or (vmid < ve and (target-ve) * (target - vmid) > 0):
                    e = mid-1
                else:
                    s = mid+1
            return -1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.