Vanilla Binary Search - Binary Search / Overview

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:

  1. 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);

  2. 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!

  1. “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