Vanilla Binary Search - Binary Search / Overview

In the binary search algorithm, why are we adding the left pointer when calculating the midpoint? A thorough example would be appreciated:
let mid = left + Math.trunc((right - left) / 2);

1 Like

The first thing that’s checked is whether or not the newly calculated mid is equal to our target answer. If it’s not, it’s recalculated based on the new “window” with different right or left.

Suppose we then truncate the left side of the range all the way up to mid. Do we need to check include this mid in the calculation of new mid in the next step? No, because we just checked that it’s not the target (first thing that was checked) so we can skip it.

Thus, when removing all elements to the left of mid we move the left boundary right by one and when moving the right boundary left of mid we decrease it by one (if you mix these up, you’ll be including even more already-tested-range)

Sorry, I misunderstood the question. Here’s a thorough answer -

1 Like

It is because you need to run the array keeping Its full length. For example, you have the array [0, 19, 21, 22, 34, 50], the indexes correspond to 0 => 5, so the calculation to refer to different points in the array would be:

  • start + (end - start) / 2, in other words, 0 + (5 - 0) / 2;

After you do the first mid, we will have 2 as a middle, or 22. Let’s suppose we’re looking for 34. Now our left need to “move” to our mid, now our left is 2 and our end still is 5. Calculating the new mid would be:

  • start + (end - start) / 2, in other words, 2 + (5 - 2) / 2;

exactly, I have the same question.

@alateos, the midpoint index must be relative to the original array

If left and right are big enough, there will be a memory leak when you do the (left + right) portion of Math.trunc((left + right)/2)

left + Math.trunc((right - left)/2) had the advantage of never running into this problem while still being equivalent to (left + right)/2

1 Like

Why would " left + ((right - left) / 2).toFixed(0) " not be a viable solution for assigning the mid variable? Is there a difference between using .toFixed() and Math.trunc()?

For C++ , may I suggest you to add: "using namespace std” to all of your solutions? Since the goal here is interview prep & ideally, we want to write less “verbose” code with minimal overheads of C++ in the limited time available during an interview. Can you help comment & address this?

{I understand, mostly the task here is to fill in the function body which may not require “std::”, but for some problems we might need to use containers and can definitely avoid writing "std::’ every time. Also, starting solution templet can look less verbose with just use of ‘using namespace std’ at top! Thoughts?}

Thank you for pointing out and we will consider it.

I have a question on the index position of the middle.

int mid = left + (right - left) / 2;

Will it is possible to use `int mid = left + (right - left) / 2 + 1;`?

Great… Thank you for considering this :)! Would be great if you can help comment on ETA.

could be done recursively too:

function binarySearch(arr, target) {
function halfAndSearch(array) {
if(array.length === 1 && arr[0] !== target) { return -1 } else {
const idx = Math.floor(array.length / 2);
if(array[idx] === target) return arr.indexOf(target);
return halfAndSearch(target < arr[idx] ? array.slice(0,idx) : array.slice(idx));
return halfAndSearch(arr);

@mod: I am not able to see the solutions that I had written in the Try it yourself section. I was able to see all of my solutions written in “Try it yourself , but now it has disappeared”. Please let me know how to fix this ?

Hi Masujkule,

I initially tried a recursive approach but I finally fell back to the method explained in the article because, with larger inputs, I would have memory exhaustion and call stack size issues =>

see the failed tests here =>

Did I miss something that prevents the recursive approach to work correctly with large inputs ?

All your tests are even numbers of numbers, Try testing with an small odd number of inputs, like 5, if that works you’re probably just running out of memory as each recurse takes some memory.

all of your short arrays tests are len(arr) % 2 == 0 i mean

can be done using recurssion

 public static int BinarySearch(List<int> arr, int target)
        int left =0;
        int right =arr.Count-1;
       return BinarySearch(arr,  target,left,  right);
     private static int BinarySearch(List<int> arr, int target,int left, int right)
            int mid =(left+right)/2;
                return mid;
               return BinarySearch(arr, target,mid+1,right);
               return  BinarySearch(arr, target,left,mid-1);
        return -1;
1 Like

I think this will throw index out of bound exception for arrays.