CODEWITHSUNDEEP
pythonarraysalgorithmsorting
Dec0de
Dec0de

Reputation: 401

Binary Search in Python: correct slicing

Please, help me unterstand the silly question about how binary sort algorithm's works. So, lets take input array of [4, 5, 6, 7, 8, 11, 20] where i'm searching for index of 6 value (see the code). As I take it should work this way:

  1. First of all we take the pivot(middle) point of (end-start)/2=7 as of index=3
  2. After the first iteration we got array's slice of [4, 5, 6] where we searching the mid point again. With result of index=1 and value = 5.
  3. After second iteration we get the only array of 6, which meets the basic condition and we getting correct result.

To prove my assumption I added an output of the cutted array I should get at the second and third step. But surprisingly it was [4, 5] on the 2nd and [] on the third step in opposite to [4,5,6] and [6] I expected?

Relating to slicing documentation a[start:stop] # items start through stop-1, so the last one isn't included.

But how homes, I'm getting the correct result assuming i'm working with [4,5,6] and [6] in opposite to incorrect output?

The code is:

def binarySearch(arr, start, end, x):
  print('the input array is: ' + str(arr[start:end]))  
  if end>=start:
    mid_idx=(start+end)//2
    print('mid index is: ' + str(mid_idx))
    if arr[mid_idx]==x:
      return mid_idx
    elif arr[mid_idx]>x:
      return binarySearch(arr,start,mid_idx-1, x)
    else:
      return binarySearch(arr,mid_idx+1,end, x)
  else:
    return None

arr=[4, 5, 6, 7, 8, 11, 20]
res=binarySearch(arr, 0, len(arr),6)
print(res)

The output is:

the input array is: [4, 5, 6, 7, 8, 11, 20]
mid index is: 3
the input array is: [4, 5]
mid index is: 1
the input array is: []
mid index is: 2
2

Upvotes: 2

Views: 160

Answers (1)

trincot
trincot

Reputation: 350841

It is good that you are surprised, because the code is not correct. It mixes two ways to interpret the end argument. Some implementations will treat end as included in the range to consider, while others treat end as the index after the intended range (this way is how slices/ranges are defined in Python).

The mix in your code can be seen here:

  • The calling code assumes the end argument as after the range
  • Your debugging print assumes the end argument as after the range
  • The first ("left") recursive call assumes the end argument is inclusive
  • The if condition assumes the end argument is inclusive.

You obviously cannot mix the two approaches and must make changes to make it consistent.

So either (excluding):

def binarySearch(arr, start, end, x):
  print('the input array is: ' + str(arr[start:end]))  
  if end>start:
    mid_idx=(start+end)//2
    print('mid index is: ' + str(mid_idx))
    if arr[mid_idx]==x:
      return mid_idx
    elif arr[mid_idx]>x:
      return binarySearch(arr,start,mid_idx, x)
    else:
      return binarySearch(arr,mid_idx+1,end, x)
  else:
    return None

arr=[4, 5, 6, 7, 8, 11, 20]
res=binarySearch(arr, 0, len(arr),6)
print(res)

Or (including):

def binarySearch(arr, start, end, x):
  print('the input array is: ' + str(arr[start:end+1]))  
  if end>=start:
    mid_idx=(start+end)//2
    print('mid index is: ' + str(mid_idx))
    if arr[mid_idx]==x:
      return mid_idx
    elif arr[mid_idx]>x:
      return binarySearch(arr,start,mid_idx-1, x)
    else:
      return binarySearch(arr,mid_idx+1,end, x)
  else:
    return None

arr=[4, 5, 6, 7, 8, 11, 20]
res=binarySearch(arr, 0, len(arr)-1,6)
print(res)

Upvotes: 4

Related Questions