704. Binary Search

📝 Problem Details

• Title: 704. Binary Search
• Link: https://leetcode.com/problems/binary-search/
• Difficulty: Easy
• Tags/Categories: Binary-Search

💭What Were My Initial Thoughts?

- array is sorted
- we are looking for a target value
- naive approach would be to iterate through the list and find the target
- since we need to write an algorithm with O(log n) runtime, a linear search isnt enough
- employ a simply binary search to find the target

💡 Explanation of Solution

- establish left and right pointers
	- set to 0 and the last value in the list
- while left <= high
	- init a mid point value that is:
		- mid = left + (right - left) / 2
	- if mid == target, return mid
	- if mid < target, make left = mid + 1
	- if mid > target, make right = mid - 1

- continue until target is found or cannot be located, in that case return -1

⌛ Complexity Analysis

Time Complexity: O(log n)

Space Complexity: O(1)

💻 Implementation of Solution

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