Does this Binary Search code work in every case? Formulate a Scientific Hypothes

Question

Does this Binary Search code work in every case?
Formulate a Scientific Hypothesis and then test it.
Determine where (if anywhere) the problem lies and refine the model (code).

Binserch(int A[],   int n, int value) {
      low = 0
      high = n - 1
      while (low <= high) {
          mid = (low + high) / 2
          if (A[mid] > value)
              high = mid  
          else if (A[mid] < value)
              low = mid
          else
              return mid
      }
      return not_found // value would be inserted at index "low"
}



1. Make a hypothesis of where (where in the code OR which cases of input) trouble occurs.
Then test each hypothesis with an experiment (for the input data or hypothetical cases).  
If you have no hypothesis after thinking a while, try experiments to help formulate one.

2. Do tests to verify the code or what the exact problem is.
    Make sure your theories have been confirmed by sufficient tests.

Explanation / Answer

No, the algorithm won't work for the cases in which the key is present at the last index of the array.

If A[mid] > value, we need to check only the elements from low to mid - 1.
If A[mid] < value, we need to check only the elements from mid + 1 to high

Correction:

Binserch(int A[], int n, int value) {
low = 0
high = n - 1
while (low <= high) {
mid = (low + high) / 2
if (A[mid] > value)
high = mid - 1
else if (A[mid] < value)
low = mid + 1
else
return mid
}
return not_found // value would be inserted at index "low"
}

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.