1

why is the terminating condition of the binary search is activated when (low>high), i have searched on the internet and everyone say that it indicates that the array is empty, but i think the array is empty when low is equal to high, N.B: low is the starting index and high is the ending index.

Nader Atef
  • 27
  • 4
  • 2
    Depends on whether the [range is open or closed](https://en.wikipedia.org/wiki/Interval_(mathematics)#Notations_for_intervals). – user3386109 Jun 23 '20 at 21:31
  • 2
    In C++ using iterator conventions low(begin) == high(end) means empty. But it's easy to make it work the other way too, you just have to be consistent everywhere. Getting this wrong is a quick way to have bugs, including infinite loops or plain wrong answers. – Mark Ransom Jun 23 '20 at 21:41
  • I find it really annoying when people write a binary search like that: https://stackoverflow.com/questions/39416560/how-can-i-simplify-this-working-binary-search-code-in-c/39417165#39417165 – Matt Timmermans Jun 24 '20 at 02:54
  • @MattTimmermans I've always found it easier to write a binary search with low and high both being inside the search range. I imagine it's a personal preference. – Mark Ransom Jun 24 '20 at 20:58
  • For an interesting take on the difficulty of writing a binary search, see https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/ – Mark Ransom Jun 24 '20 at 22:05

2 Answers2

0

you are not wrong. the array is empty when low is equal to high. but for this condition (low>high) to be true, low would first have to be equal to high. So the two statements are both correct in a way

Ebenezer Mathebula
  • 271
  • 1
  • 5
  • 19
0

It depends on meaning of high. If high is last index (not a length of interval) then condition should be (low<=high). My choice is to use "last index" because when you calculate mid you refer by high as array[high].

Leon .Leon
  • 11
  • 3