CODEWITHSUNDEEP
pythonbinary-searchdivide-and-conquer
Joan Dimko
Joan Dimko

Reputation: 115

binary search using divide and conquer technique

Algorithm is working but can only find if the value exist or not. I want to find the index in case it exists. How can I do it?

def binarySearch(arr, num):
  if len(arr) == 1: #base case
    if arr[0] == num:
      return arr[0] #found
    else:
      return None #not found

  mid = int(len(arr)/2) 
  if arr[mid] > num:
    return binarySearch(arr[:mid], num)
  else:
    return binarySearch(arr[mid:], num)

print(binarySearch([1,2,3,4], 7)) #None
print(binarySearch([1,2,3,4], 3)) #3
print(binarySearch([1,2,3,4], 4)) #4
print(binarySearch([1], 2)) #None
print(binarySearch([1,2], 2)) #2

Upvotes: 0

Views: 1329

Answers (1)

jsmolka
jsmolka

Reputation: 800

Just pass the index around like this:

def binarySearch(arr, num, idx=0):
  if len(arr) == 1: #base case
    if arr[0] == num:
      return idx
    else:
      return None #not found

  mid = len(arr) // 2
  if arr[mid] > num:
    return binarySearch(arr[:mid], num, idx)
  else:
    return binarySearch(arr[mid:], num, idx + mid)

print(binarySearch([1,2,3,4], 7)) #None
print(binarySearch([1,2,3,4], 3)) #2
print(binarySearch([1,2,3,4], 4)) #3
print(binarySearch([1], 2)) #None
print(binarySearch([1,2], 2)) #1

It now returns the index of the number if it has been found or None if it's not in the list.

As mentioned in the comments: consider passing start and end values instead of copying the list at every recursion. It's faster and easier to write and to read.

Upvotes: 1

Related Questions