Nerd For Tech
Published in

Nerd For Tech

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:

Example 2:

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.

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

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Sukanya Bharati

Sukanya Bharati

152 Followers

A happy , motivated & a curious soul if you end up finding me 😎😁.