In binary search, we usually have low and high variables and typically there is a while loop that tests if low <= high, as shown in this code (from Wikipedia):
int SortedArray[max] = {....}
int BinarySearch (int key)
{
int start = 0;
int end = max - 1;
int mid;
while (start <= end)
{
mid = (start + end) / 2;
if (key == a[mid])
return mid;
else if (key < a[mid])
end = mid - 1;
else start = mid + 1;
}
return -1;
}
When learning binary search, I was always taught the start <= end approach, but when seeing other implementations, I've seen a lot of people do while(start < end).
Is there an advantage to one versus the other? In my own native implementations, I do the <= approach but when I switch it out for <, the search fails.
Is there a rule of thumb for using one versus the other?
even if your question is probably not super clear, I could infer you are talking about this kind of implementation of the binary search (here in C, from Wikipedia):
int SortedArray[max] = {....}
int BinarySearch (int key)
{
int start = 0;
int end = max - 1;
int mid;
while (start <= end)
{
mid = (start + end) / 2;
if (key == a[mid])
return mid;
else if (key < a[mid])
end = mid - 1;
else start = mid + 1;
}
return -1;
}
If you replace start <= end by start < end, there will be cases where your algorithm will not give the good answer.
Let's think about two cases.
1 - You would like to search 1 in the list [1]. In that case, start = 0, end = 0 and the algorithm would return -1 if you change the loop condition.
2 - You would like to search 2 in the list [1, 2]. In that case, start = 0, end = 1. The algorithm will set mid = (0+1)/2=0 in C. Thus arr[mid] < key. It will make start = 1, end = 1. Again, if you stop the loop here, the algorithm will return -1 instead of 1.
And there are probably many other examples.
Have a nice day