Problem Statement:-
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.
Link: https://leetcode.com/problems/binary-search/description/
Problem Explanation with examples:-
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<sup>4</sup>-10<sup>4</sup> < nums[i], target < 10<sup>4</sup>All the integers in
numsare unique.numsis sorted in ascending order.
Intuition:-
Its a sorted array and the best search algo for sorted array is binary search.
Simply find the mid and check if its the target, if not, then reduce the search space by half depending on the target and mid value.
Solution:-
Initialize l and r to 0 and n-1 respectively.
While l <= r, find the mid by (l+r)//2.
If nums[mid] == target, return mid.
If nums[mid] > target, then reduce the search space by half by setting r = mid-1.
If nums[mid] < target, then reduce the search space by half by setting l = mid+1.
If the target is not found, return -1 after the while loop.
Code:-
JAVA Solution
class Solution {
public int search(int[] nums, int target) {
int s=0;
int e=nums.length-1;
int m = (s+e)/2;
while(s<=e){
m = (s+e)/2;
if(nums[m] == target)
return m;
else if(nums[m] < target)
s = m+1;
else{
e = m-1;
}
}
return -1;
}
}
Python Solution
class Solution:
def search(self, nums: List[int], target: int) -> int:
n = len(nums)
l = 0
r = n-1
while l <= r:
m = (l+r)//2
if nums[m] == target:
return m
elif nums[m] > target:
r = m-1
else:
l = m+1
return -1
Complexity Analysis:-
TIME:-
The time complexity is O(logn) where n is the length of the array nums as we are reducing the search space by half at every step.
SPACE:-
The space complexity is O(1) as we are not using any extra space.