704. Binary Search

(LeetCode easy problem)

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 <= 104
• -104 < nums[i], target < 104
• All the integers in nums are unique.
• nums is sorted in ascending order.

First of all, let us understand what do we mean by a binary search and how does it work?

The only condition that is required for a binary search to work is that array elements must be sorted either in an ascending or descending order.

Let us say for example the array is sorted in increasing order, nums = [1,2,3,4,5,6,7]. So now let us say we need to find that number 6 exists or not and if it exists then at what position.

This is what exactly binary search looks like, it divides the array into two parts and ends up only traversing that part of the array which fulfills its basic requirements.

Every time it traverses it keeps on diving the array into half which reduces the time complexity in a generic manner if you had to traverse the whole array in case of linear search.

This is the below code for binary search. Since I have already told you the way how to go by the logic I would want you to do a quick dry run of as many examples you can, this will strengthen your concept and obviously clear it out on your basics of the working of this algorithm.

So here the time complexity of the binary search is O(logN) where N is the size of the array and space complexity is O(1).

The best time complexity comes down to O(1) when the array element to be found is present in the middle of the array.

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

Hope you are enjoying your time reading through the basics of the fundamental algorithms and getting a clear concept of how to solve them as well. Kudos to you, keep learning! 🙌💻

Stay tuned for more such articles coming up!! Cheers!!

If you enjoyed reading my blog , why not buy me a coffee and supoort my work here!! https://www.buymeacoffee.com/sukanyabharati ☕