Binary Search - Leet Code

This article is another part of a series on leet code problems solutions, and it provides a solution to the leet code Binary Search problem. This is a Leet code problem named Binary Search. We will solve it using python and it is the best space and time optimized solution.

Question of Binary Search 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

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

Approach to solve Two Sum Problem

In binary search, we have always sorted arrays so that we will half the array in each iteration. In each iteration, we will find the middle element and check if it is equal to the target number or not. Then we further divide the array and limit our search to half of the array.

Variables and its usage

We are using three extra variables here. They are the start, end, and mid.

Start : This variable is used to store the starting index of the array.
End : This variable is used to store the lastindex of the array.
Mid : This variable is used to store the mid of start and end.

Algorithm For Binary Search

Below is the of step by step algorithm :

Store the start and end index in the start and end variable.
Repeat the steps from 3 to 6 till the start is less than or equal to the end.
Find the mid using formula (start+end)/2.
Check if the element at position mid is equal to the target element. If yes then return the mid and break for a loop.
Otherwise, check if the element at mid is greater than the target number. If yes then set the end to mid-1.
Otherwise set the start to mid+1.
End of while loop

Python Code for Binary Search


def BinarySearch( arry, target )  :
    # we will solve this question by binary search
    #staring index of array
    start = 0
    #last index of an array
    end = len(arry) -1
    
    #run for loop untill start < end
    
    while(start<=end):
        #find mid position of array
        mid = (start+end)//2
        
        #check if target number exists in mid position
        if(arry[mid] == target):
            return mid
        elif(arry[mid] > target):
            end = mid-1
        else:
            start = mid+1
    # if we arrive here then we didnt find the number
    #so we return -1
    return -1
        
            
#Main function

arr = [ 2, 3, 4, 10, 40 ,50,60,80,90 ]
x = 3
 
# Function call
result = BinarySearch(arr, x)
 
if result != -1:
    print("Element is present at index", str(result))
else:
    print("Element is not present in array")