LeetCode Questions — Day 1 (Binary Search)

Hi Coders,
I recently started solving problems in the leetcode, so I thought to share the questions and the way I approached initially to the problems. I will also provide you all with the optimised solutions.

Ques-1 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 Approach:

Explanation: In this approach, I am simply iterating over the each element of the array and looking for the target, whenever i am getting the target matched I am returning the index value.

Second Approach:

Explanation: Using Binary Search, This approach was the efficient one which took half time as comparing to mine approach.
Note:
Binary Search includes the following the steps:
1.Compare x with the middle element.
2.If x matches with the middle element, we return the mid index.
3.Elif (x is smaller) If x is smaller than the mid element, then x can only lie in the left half subarray before the mid element. recur for the left half.
4.Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for the right half.

Ques-2 : You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimise the number of calls to the API.

Example 1:
Input: n = 5, bad = 4
Output: 4
Explanation:
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true
Then 4 is the first bad version.

Example 2:
Input: n = 1, bad = 1
Output: 1
Constraints:

• 1 <= bad <= n <= 231 - 1

First Approach and Final Approach:

Explanation: In this Approach again we are using binary search.
But how things are working is : Initially we are getting the mid value and sending that mid value to isBadVersion function to check for the False version. If that becomes False meaning that till that position there was not bad versions. so we will start our search from the mid+1 till the last element. This will get continue till our start becomes greater than end.
At the end when it becomes greater than end we will get out of the loop with the first bad version.

Now you all will be thinking, in the second approach how could i get the optimised solution first, well there is nothing to get surprised on that since the last question i did, in the second approach itself i used binary search so my mind first clicked that only as a approach to solve this problem.

Hope this was useful for you all,
May be my code logic will look like a basics one but this is the only way how we start initially, let’s start together and grow together.

Keep Reading, Keep Coding….