Table of Contents
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
numsare unique. numsis 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 –
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