Guidelines

Binary search implementation:

Java

public int search(int[] nums, int target) {
    int low = 0, high = nums.length - 1;

    while(low <= high){
        int mid = low + (high-low)/2; // coping with overflow
        if(nums[mid] == target){
            return mid;
        }
        else if(nums[mid] < target){
            low = mid + 1;
        }
        else{
            high = mid - 1;
        }
    }

    return -1;
}

JavaScript

const search = (nums, target) => {
  let low = 0;
  let high = nums.length - 1;

  while (low <= high) {
    let mid = Math.floor(low + (high - low) / 2); // coping with overflow
    if (nums[mid] === target) {
      return mid;
    } else if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
};

Python

def search(nums, target):
    low = 0
    high = len(nums) - 1

    while low <= high:
        mid = (low + high) // 2  # coping with overflow
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1

C++

int search(vector<int>& nums, int target) {
    int low = 0;
    int high = nums.size() - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2; // coping with overflow
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }

    return -1;
}

Wherever there is a mention of some order (partial or full) or even some kind of releation between successor and predecessor think about how can you eliminate some parts of the search space using (modified) binary search. There are actually only three things you need to get right when implementing binary search:

• initial boundaries
• definition of invariants (e.g. while(low <= high))
• trial function (some calculation to check if the mid is the best element or if and how we should move to left or right in search space)

while(start <= end)  // if you're returning solution from the loop
while(start < end) // if you're returning after the loop

Java

// built in binary search
int idx = Arrays.binarySearch(sums, element); // returns the index of found element or insertion point if not found (negative index)
return idx >= 0 ? idx : ~idx;

// for array of complex objects
int idx = Collections.binarySearch(map.get(key), new Pair("", timestamp), (a, b) -> a.timestamp - b.timestamp);

JavaScript

// Built-in binary search
let idx = sums.indexOf(element);
return idx >= 0 ? idx : -idx - 1;

// For an array of complex objects
let idx = map.get(key).findIndex((item) => item.timestamp === timestamp);
return idx >= 0 ? idx : -idx - 1;

Python

# Built-in binary search
idx = bisect.bisect_left(sums, element)
return idx if idx < len(sums) and sums[idx] == element else -idx - 1

# For an array of complex objects
lst = map.get(key)
idx = bisect.bisect_left(lst, Pair("", timestamp), key=lambda item: item.timestamp)
return idx if idx < len(lst) and lst[idx].timestamp == timestamp else -idx - 1

C++

// Built-in binary search
auto it = std::lower_bound(sums.begin(), sums.end(), element);
int idx = it - sums.begin();
return idx < sums.size() && sums[idx] == element ? idx : -idx - 1;

// For an array of complex objects
auto& lst = map[key];
auto it = std::lower_bound(lst.begin(), lst.end(), Pair("", timestamp), [](const auto& a, const auto& b) {
    return a.timestamp < b.timestamp;
});
int idx = it - lst.begin();
return idx < lst.size() && lst[idx].timestamp == timestamp ? idx : -idx - 1;

• |a - x| < |b - x| interval search Find K Closest Elements
• binary search on two arrays Median of Two Sorted Arrays