What's wrong with my program? It is always returning "not found"

Question

Check out my problem at: https://github.com/harishsambasivam/SearchingAlgorithms/blob/master/BinarySearch-RecursiveMethod.js

function BinarySearch(low, high, key, arr) {
  if (low > high) return 'Not Found';
  if (low === high) {
    if (arr[low] === key) return "Found";
    else return "Not found";
  } else {
    var mid = Math.abs((low + high) / 2);
    if (arr[mid] === key) return "Found";
    else if (arr[mid] > key) return BinarySearch(low, mid - 1,
      key, arr);
    else return BinarySearch(mid + 1, high, key, arr);
  }
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8];
console.log(BinarySearch(0, 7, 5, arr));

I expected both "found" and "not found", but only "not found" is being returned.

score 2 · Answer 1 · answered Jun 10 '19 at 06:11

2

I think that the main problem is from your mid value calculus.

console.log(Math.abs((0 + 7) / 2)) //==> 3.5

And for the next iteration the value will be /w decimals. You can fix that first.

You can fix that by: Math.trunc((min + high) / 2);

answered Jun 10 '19 at 06:11

Marc Moldovan

83
10

Not much sense in using an ES6 math function when an ES1 function would suffice. – JLRishe Jun 10 '19 at 06:17
3

I think both are okay. I think we need to drive adoption of ES6 and get browsers to improve their implementations rather than resorting to old features. – Avin Kavish Jun 10 '19 at 06:23

score 2 · Answer 2 · answered Jun 10 '19 at 06:14

You're using Math.abs when you should be using Math.floor, and that is why it's not working. Using Math.abs is pointless here since low and high are always nonnegative.

function BinarySearch(low, high, key, arr) {
  if (low > high) return 'Not Found';
  if (low === high) {
    if (arr[low] === key) return "Found";
    else return "Not found";
  } else {
    var mid = Math.floor((low + high) / 2);
    if (arr[mid] === key) return "Found";
    else if (arr[mid] > key) return BinarySearch(low, mid - 1,
      key, arr);
    else return BinarySearch(mid + 1, high, key, arr);
  }
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8];
console.log(BinarySearch(0, 7, 5, arr));

Hardik Leuwa · Answer 3 · 2019-06-10T06:51:15.750

0

You can use other Math functions instead of Math.floor by refer this link https://stackoverflow.com/a/596503/6517783

function BinarySearch(low, high, key, arr) {
  if (low > high) return 'Not Found';
  if (low === high) {
    if (arr[low] === key) return "Found";
    else return "Not found";
  } else {
    var mid = Math.floor((low + high) / 2);
    if (arr[mid] === key) return "Found";
    else if (arr[mid] > key) return BinarySearch(low, mid - 1,
      key, arr);
    else return BinarySearch(mid + 1, high, key, arr);
  }
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8];
console.log(BinarySearch(0, 7, 5, arr));

edited Jun 10 '19 at 06:51

answered Jun 10 '19 at 06:21

Hardik Leuwa

3,282
3
14
28

Why are you using `Math.abs` and `Math.floor` ? – Avin Kavish Jun 10 '19 at 06:24
For convert float value to integer. Because in next statement value is using as array index – Hardik Leuwa Jun 10 '19 at 06:25
Why do you need `Math.abs` for that ? – Avin Kavish Jun 10 '19 at 06:25
`Math.abs` will use to convert negative value to positive – Hardik Leuwa Jun 10 '19 at 06:29
But the values well never be negative in this case. – Avin Kavish Jun 10 '19 at 06:30
Yes, the solution is not only for single selected values. In question he is asking that his program always return "Not Found" i don't think his mean to say for single value. He must be tried with many different values and he gives a sample in snippet – Hardik Leuwa Jun 10 '19 at 06:32

score 0 · Answer 4 · answered Jun 10 '19 at 06:29

0

Here in mid value, you will get value in decimals which cannot select any arr[mid] element. So, for that, you can change the math.abs to math.floor/ math.ceil as per your requirement.

answered Jun 10 '19 at 06:29

Varun Raval

134
6

What's wrong with my program? It is always returning "not found"

4 Answers4