Binary Search LeetCode Solution


Frequently asked in Adobe Amazon Apple Bloomberg Google Infosys Microsoft Samsung SAP TCS Yahoo Yandex
Categories - Easy Goldmann SachsViews 5233

Problem Statement

Binary Search LeetCode Solution says that – 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.

ALGORITHM –

IDEA  –

  • In order to use Binary Search for finding the target element . First we will use Binary Search algorithm first we will find the middle element of an array and if middle element is equal to target element Then basically we will return index of that element.
  • If middle element is smaller than than target element then we will check in second half only.
  • Else we will Check in the first- half and this process continue until low > high.

APPROACH –

  • At first we will use Binary Search algorithm and we will take two variable low = 0 and high = length of array -1.
  • After that we will use while condition while(low <= high) and within that condition we will find middle element each time.
  • If middle element is Equal to Target then we will return the middle element index.
  • Else if middle less than Target then we will check in second half only i.e. low = mid+1.
  • Else we will check in first half i.e high = mid-1.
  • At last return the index of element and if its not found then we will return -1.

Image of the solution –

Binary Search LeetCode Solution

class Solution {
    public int search(int[] nums, int target) {
        
        
        int low = 0;
        int high = nums.length-1;
        while(low <= high){
            
            int mid = (low+high)/2;
            if(nums[mid] == target){
                return mid;
                    
            } 
            
            else if(nums[mid] < target){
                low = mid+1;
            }
            else
                high = mid-1;
        }
        
        return -1;
        
        
    }
}
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        low = 0
        high = len(nums)-1
        
        while(low <= high):
            mid = (low+high)//2
            if nums[mid] == target:
                return mid
            
            elif nums[mid] < target:
                low = mid+1
            
            else:
                high = mid-1
        return -1

Time Complexity – O(LOGN), As we have used binary search in this question.

Space Complexity – O(1), As we have not taken any extra space.

Similar question – https://tutorialcup.com/interview/linked-list/finding-middle-linkedlist.htm

Translate »