Binary Search

binary-search • array
Easy
O(logn)O(log n)

Implement binary search to find a target in a sorted array.

Solution

Use two pointers (low, high) and repeatedly narrow the search window by comparing mid to target.
Return the index if found, otherwise -1.

Code Solution

binary-search.cpp
cpp
1
#include <vector>
2
using namespace std;
3


4
int binarySearch(const vector<int>& nums, int target) {
5
  int lo = 0, hi = (int)nums.size() - 1;
6
  while (lo <= hi) {
7
    int mid = lo + (hi - lo) / 2;
8
    if (nums[mid] == target) return mid;
9
    if (nums[mid] < target) lo = mid + 1;
10
    else hi = mid - 1;
11
  }
12
  return -1;
13
}