704. Binary Search

---

My Solution

The Key Idea for Solving This Coding Question

Because the integers in nums are sorted in ascending order, we can use binary search to find target.

C++ Code 1

class Solution {
public:
    int search(vector<int> &nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] < target) {
                left = middle + 1;
            } else if (target < nums[middle]) {
                right = middle - 1;
            } else {
                return middle;
            }
        }
        return -1;
    }
};

C++ Code 2

class Solution {
public:
    int search(vector<int> &nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int middle = left + (right - left) / 2;
            if (nums[middle] < target) {
                left = middle + 1;
            } else {
                right = middle;
            }
        }

        if (nums[left] == target) {
            return left;
        }
        return -1;
    }
};

Time Complexity

$O(logn)$

$n$ is the length of nums.

Space Complexity

$O(1)$

Miscellane