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);
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 - https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
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
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 => https://github.com/yactouat/algos/commit/a4ead03aae80847977caa646db0bba7d044624be#diff-dcdc3e0b3362edb8fec2a51d3fa51f8fb8af8f70247e06d9887fa934834c9122R17
see the failed tests here => https://github.com/yactouat/algos/commit/a4ead03aae80847977caa646db0bba7d044624be#diff-d86f4a82fca0b37a584662be5f1e76e8e729ae0d8a63b381dee9d840f49e1fabR41
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)
{
// WRITE YOUR BRILLIANT CODE HERE
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)
{
if(left<=right)
{
int mid =(left+right)/2;
if(arr[mid]==target)
{
return mid;
}
if(target>arr[mid])
{
return BinarySearch(arr, target,mid+1,right);
}
else{
return BinarySearch(arr, target,left,mid-1);
}
}
return -1;
}
I think this will throw index out of bound exception for arrays.