There is a binary search algorithm, which, depending on the value of the last variable, returns the first or last entry of the element into the array

 def binary_search(l, key, last): low = 0 high = len(l)-1 while low <= high: mid = (low + high) // 2 midVal = l[mid]; if (midVal < key or (last and midVal == key)): low = mid + 1 elif (midVal > key or ((not last) and midVal == key)): high = mid - 1 return high if last else low

How to add a check for the existence of an element in the binary search algorithm?

  • if midval == key: - 0andriy
  • @ 0andriy does this mean the existence of an element in an array? - pinguin

1 answer 1

Alternatively, after the completion of a while , you can check the equality of the values ​​by key and in the absence of it, return None :

 def binary_search(lst, value, is_last): low = 0 high = len(lst) while low <= high: mid = (low + high) // 2 mid_val = lst[mid]; if (mid_val < value or (is_last and mid_val == value)): low = mid + 1 elif (mid_val > value or ((not is_last) and mid_val == value)): high = mid - 1 else: if is_last and high == value: return high elif not is_last and low == value: return low else return None