Examples

Binary Search on a Sorted Array

Quick review - We are cutting the range in half with each iteration of the for loop (standard stack of papers analogy). If the target is not in our half, then we search the other half.

DS&A tip - One key is probably getting comparison operators correct. This is likely a common point of failure. Log out the ranges for verification

def binary_search(arr, target):
    start, end = 0, len(arr) - 1

    while start <= end:
        mid = start + (end - start) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return -1  # Element not found

function binarySearch(arr, target) {
    let start = 0;
    let end = arr.length - 1;

    while (start <= end) {
        let mid = Math.floor((start + end) / 2);
        if (arr[mid] === target) {
            return mid;  // Target found
        } else if (arr[mid] < target) {
            start = mid + 1; 
        } else {
            end = mid - 1;
        }
    }

    return -1;  // Element not found
}

#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int start = 0;
    int end = arr.size() - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] == target) {
            return mid;  // Target found
        } else if (arr[mid] < target) {
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return -1;  // Element not found
}

func BinarySearch(arr []int, target int) int {
    start, end := 0, len(arr)-1

    for start <= end {
        mid := start + (end-start)/2
        if arr[mid] == target {
            return mid // Target found
        } else if arr[mid] < target {
            start = mid + 1
        } else {
            end = mid - 1
        }
    }

    return -1 // Element not found
}

Notes

• In javascript we need to use Math.Floor, In python we have the // operater which does the flooring for us. In both C++ and Go the variable we are assigning to is an integer and the remainder is dropped... this is kinda nice that we don't have to worry about unintentional floats.
  • Curiosity: What would happen if we tried to index into an array with a float in javascript??? (Hint: It's not what you would think)