Python Binary Search Mid calculation-CodePudding

Why " mid = (high low) // 2 " instead of " mid = high//2 " ? I can't fully understand why they use mid = (high low)//2 If anybody can demystify my understanding of this, that would be greatly appreciated :)

# Iterative Binary Search Function
# It returns index of x in given array arr if present,
# else returns -1
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    mid = 0

    while low <= high:

        mid = (high   low) // 2

        # If x is greater, ignore left half
        if arr[mid] < x:
            low = mid   1

        # If x is smaller, ignore right half
        elif arr[mid] > x:
            high = mid - 1

        # means x is present at mid
        else:
            return mid

    # If we reach here, then the element was not present
    return -1


# Test array
arr = [ 2, 3, 4, 10, 40 ]
x = 10

# Function call
result = binary_search(arr, x)

if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")

CodePudding user response：

Because both low and high are moving when your algorithm plays out. mid is not the strict middle of the array, it's the middle of the rest of the values you have to search through: the middle between low and high. Thus we compute the average: (low high) // 2 to get mid.

To better visualize the problem:

CodePudding user response：

(high low) // 2 ensures the mid index is within the range of low and high. If you don't use low in your mid calculation, you could end up with a result where mid < low, which breaks the binary search because you stop searching within the range of values you've already narrowed it down to.

CodePudding user response：

Let's say you want to search in [5, 4, 7, 8, 1, 2, 11, 12] indices will be: [0, 1, 2, 3, 4, 5, 6, 7]

For binary search, we have to divide it in half.

middle element : mid = (high low )/ 2

here high = 7 and low = 0, hence you might be thinking why do we even need to use low when it is zero.

But when we have to divide the second half of the array further, i.e. [1, 2, 11, 12] with indices [4, 5, 6, 7]

mid = (high low) / 2 high = 7, low = 4, hence mid = 6. Here you cannot do mid = high/2. You can see the difference. It helps to get to the right middle place for all the halves.

CodePudding user response：

a=[2, 3, 4, 10, 40]

while doing binary search on this array for 10 watch closely at the value of high,low and mid you will get it why do we use it

high = 4
low  = 0 
mid = 2

now as the value on mid is less than 10 we will change the mid with low

low = 2
high = 4
mid = 3

hence found the number

as you can see why we put low to calculate the mid value if we do not do this mid will all the time come 2 for this case and we will not be able to traverse in the array .