Implementing binary search to find index?

Question

So I understand conceptually how binary search works, but I always have problems with implementing it when trying to find an index in an array. For instance, for the Search Insert Position on LC, this is what I wrote:

def searchInsert(self, nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    """
    if target > nums[-1]:
        return len(nums)
    low = 0
    high = len(nums) - 1
    
    while high > low:
        mid = (low + high) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] > target:
            high = mid
        else:
            low = mid + 1
    
    return low

It works, but I don't understand why I have to update low as mid + 1 instead of updating low as mid. Similarly, why am I updating high as mid instead of mid - 1. I've tried updating low/high as every combination of mid, mid - 1, and mid + 1 and the above is the only one that works but I have no idea why.

When implementing binary search for these kinds of problems, is there a way to reason through how you update the low/high values?

You can always use bisect module built into Python, or borrow the source code from github if you need to customize it. 90% of programmers can't write it correctly. I'm probably one of them. — ggorlen
– ggorlen, Commented Sep 17, 2020 at 4:59

Joona Yoon · Accepted Answer · 2020-09-17 05:39:29Z

This is personal favorite:

while high >= low:
    mid = (low + high) // 2
    if nums[mid] >= target:
        high = mid - 1
    else:
        low = mid + 1
   
return low
# or return nums[low] == target for boolean

It has difference in the case that has same values.

for example, Let's assume the array is [1,1,2,2,3,3,3,3,4].

with your function, search(arr, 1) returned 1 BUT search(arr, 2) returned 2.

why does it returned most RIGHT index on the interval 1s, and returned most LEFT index on 2s?

As i think, the key is at if nums[mid] >= target:.

when it finds the target exactly same one, the range changes by high = mid - 1. it means high might not be answer because the answer we found is mid. [1]

At the last step of binary search, the range is going to close to zero. and finally loop breaks by they crossed. thus, the answer must be low or high. but we know high is not an answer at [1].

Collectives™ on Stack Overflow

Implementing binary search to find index?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related