Skip to content

Binary Search⚓︎

Link

Description⚓︎

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

You must write an algorithm with \(O(\log n)\) runtime complexity.

Example 1:

  • Input: nums = [-1,0,3,5,9,12], target = 9
  • Output: 4

Explanation: 9 exists in nums and its index is 4

Example 2:

  • Input: nums = [-1,0,3,5,9,12], target = 2
  • Output: -1

Explanation: 2 does not exist in nums so return -1

Constraints:

  • 1 <= nums.length <= 10^4
  • -10^4 < nums[i], target < 10^4
  • All the integers in nums are unique.
  • nums is sorted in ascending order.

Solution⚓︎

Binary Search Solution Way 1⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        return nums[l] == target ? l : -1;
    }
};

Binary Search Solution Way 2⚓︎

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = -1, r = nums.size();
        while (l + 1 < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid;
        }
        return (r < nums.size() && nums[r] == target) ? r : -1;
    }
};