Binary Search

INFO

Binary Search called “Recherche Dichotomique” in French is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half.

APPROACH

Find the Exact Value

class Solution {
public:
  int search(vector<int> &nums, int target) {
    int leftPtr = 0;
    int rightPtr = nums.size() - 1;

    while (leftPtr <= rightPtr) {
      int m = (leftPtr + rightPtr) / 2;

      if (nums[m] == target)
	return m;
      else if (nums[m] < target)
	leftPtr = m + 1;
      else
	rightPtr = m - 1;
    }
    return -1;
  }
};

Find Upper bound

class Solution {
public:
  int search(vector<int> &nums, int target) {
    int leftPtr = 0;
    int rightPtr = nums.size();

    while (leftPtr < rightPtr) {
      int m = (leftPtr + rightPtr) / 2;

      if (nums[m] == target)
	return m;
      else if (nums[m] < target)
	leftPtr = m + 1;
      else
	rightPtr = m;
    }
    if (leftPtr > 0 && nums[leftPtr-1] == target)
	return leftPtr - 1;
    return -1;
  }
};

Find Lower Bound

class Solution {
public:
  int search(vector<int> &nums, int target) {
    int leftPtr = 0;
    int rightPtr = nums.size();

    while (leftPtr <= rightPtr) {
      int m = (leftPtr + rightPtr) / 2;

      if (nums[m] < target)
	leftPtr = m + 1;
      else
	rightPtr = m - 1;
    }
    return leftPtr;
  }
};