704. Binary Search Leetcode Solution
Binary Search Leetcode 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.
Binary Search Leetcode Solution :
Constraints :
- 1 <= nums.length <= 104
- -104 < nums[i], target < 104
- All the integers in nums are unique.
- nums is sorted in ascending order.
Example 1:
- Input: nums = [-1,0,3,5,9,12], target = 2
- Output: -1
Intuition :
Binary search is an efficient algorithm for searching for a specific target value within a sorted array. The basic idea is to repeatedly divide the search interval in half until the target value is found or the interval is empty. By using this approach, we can quickly eliminate half of the remaining search space at each iteration, resulting in a time complexity of O(log n).
Approach :
The algorithm starts by comparing the target value to the middle element of the sorted array. If the target is equal to the middle element, we return the index of the middle element. If the target is less than the middle element, we repeat the search on the left half of the array. If the target is greater than the middle element, we repeat the search on the right half of the array. We continue this process until either the target is found or the search interval is empty.
Initialize left and right pointers to the beginning and end of the array, respectively.
While the left pointer is less than or equal to the right pointer:
a. Calculate the middle index as the average of the left and right pointers.
b. If the middle element is equal to the target, return the index of the middle element.
c. If the middle element is less than the target, update the left pointer to mid + 1.
d. If the middle element is greater than the target, update the right pointer to mid – 1.If the target is not found, return -1.
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
int search(vector< int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
};
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
class Solution(object):
def search(self, nums, target):
left = 0
right = len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment