The test cases need a case where the target number is at the beginning of the array. For example:
Input
2, 4, 5
2
Output
0
There should also be an empty array test case
Incorrect test cases on the first āTry it yourselfā boxā¦
Suggestion for C++ solution:
-
Pass arrays, vectors, etc. by reference and declare const arguments that arenāt supposed to be modified. Itās something the interviewer will definitely notice.
int binary_search(const std::vector& arr, const int target); -
You can use STL iterators for STL containers. In this example:
auto left = arr.begin();
auto right = arr.end() - 1;
Since iterators are defined for all STL containers, you can implement algorithms as templates!
- āUsing namespace stdā is considered a bad practice, please donāt start using it. https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice
It is usually used in tutorials to make the code more simple, but I donāt think any company uses it in the code, so it is better not to get used to it.
Just wanted to share my JS solution:
function binarySearch(arr, target, start = 0, end = arr.length - 1) {
if(start > end) {
return - 1
}
const mid = Math.floor((end + start) / 2)
const result = arr[mid]
if(result < target) {
return binarySearch(arr, target, mid + 1, end)
}
if(result > target) {
return binarySearch(arr, target, start, mid - 1)
}
return mid
}
1 Like
Nice really clean solution without the while!!
Using āusing namespace *;ā is considered bad practice due to function name collision. Explained here: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice
Binary search Python code is short and quick to understand , implement and relate to specially when new to computer science concepts.
Hereās my implementation that seemed more intuitive to me. I ended up just shifting the mid instead of the start/end.
def binary_search(arr: List[int], target: int) ā int:
start = 0
end = len(arr)
midpoint = (start + end) // 2
while midpoint < end and midpoint > start:
if target == arr[midpoint]:
return midpoint
if target < arr[midpoint]:
midpoint = (midpoint + start) // 2
if target > arr[midpoint]:
midpoint = (midpoint + end) // 2
return -1
my implementation in c#
public static int BinarySearch(List arr, int target)
{
// WRITE YOUR BRILLIANT CODE HERE
if(arr.Count <= 0)
return -1;
int length = arr.Count;
int mid = length / 2;
int midVal = arr[mid];
if (midVal == target)
return mid;
else if (midVal <target)
{
return mid + BinarySearch(arr.GetRange(mid,(arr.Count-mid)), target);
}
else if(midVal> target)
return BinarySearch(arr.GetRange(0,mid), target);
return -1;
}
Here is mine but no matter how you implement the key is:
for each Target greater than arr[x] we calc mid_right and do compare, whereas for each Target less than arr[x] we calc mid_left, until we reach to the end of the array (right seek) or the beginning of the array (left seek).
int n = arr.size();
int mid = n/2; //middle of the arr, the mid index
while(mid > 0 && mid <= n-1 ) { //Left and Right bounds, until reached to the beginning or the end of arr
if(target == arr[mid]) {
return mid; //Found!
}
if(target > arr[mid]) { //A match could be found at the upper index of the mid (Right of the mid index)
mid = mid + (n-mid)/2; //New mid. Right mid of the previous mid
}
else { // A match could be found at the lower index of the mid (Left of the mid index)
mid = mid/2; //New mid. Left mid of the previous mid
}
}
return -1;//Not Found
+1
public static int binarySearchRecursion(List arr, int target) {
if (arr.size() < 1) return -1;
if (arr.size() == 1) {
if (arr.get(0) == target) return 0;
else return -1;
}
int midIndex = arr.size() / 2;
int midVal = arr.get(midIndex);
if (arr.get(midIndex) == target) return midIndex;
else {
int startIndex = midVal > target ? 0 : midIndex;
int endIndex = midIndex > target ? midIndex : arr.size();
int subRes = binarySearchRecursion(arr.subList(startIndex, endIndex), target);
if (subRes == -1) return subRes;
else return startIndex + subRes;
}
}
your solution is wrong. you need to update the start and end pointers too
Try to avoid variables with only one word like you variable n.
Only use it for for loops that single variable names. Even for this binary search.
Q. Why all my submitted C++ code under ā// WRITE YOUR BRILLIANT CODE HEREā is missing ??? It has happened to all my other topics !! Plz tell me how to retrieve my previously submitted code!? Its really a nightmare if all the previously submitted code is lost! @All: Has any one else seen this issue and was able to retrieve?? Can I talk to someone from AlgoMonster team?
Were you ever able to retrieve your submitted solutions under "Try It Yourself"section? Am experiencing the same issue & its really a nightmare !
hey, the code is saved in localstorage. if you use the same browser it should show up. we will add server persisting in the future.
I didnāt notice AlgoMonsterās logo is a binary search illustration lol
1 Like
function binarySearch(arr, target, mid=0) {
if(target < arr[0] || target > arr[n-1]) return -1
const n = arr.length
mid = mid || Math.floor(n/2)
if(target === arr[mid]) return mid
if(target > arr[mid]){
return binarySearch(arr, target, Math.floor((mid+n)/2))
}else{
return binarySearch(arr, target, Math.floor((mid)/2))
}
}
def binary_search(arr: List[int], target: int) ā int:
if target not in arr:
return - 1
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] > target:
right = mid - 1
else:
left = mid + 1