What is Binary Search & how does it work ? 🤔
Binary Search is a searching algorithm that is applicable only to sorted arrays. It operates by repeatedly dividing the search interval in half, narrowing down the potential locations of the target value with each iteration. This cycle of dividing and searching continues until the target value has been found or until it is determined that the element is not in the array.
What is the Space & Time Complexity of Binary Search? ⏰
The average time complexity of the Binary Search algorithm is O(log N), where N is the number of elements in the array. This logarithmic time complexity arises from the fact that with each step, the search interval is halved, leading to a rapid reduction in the number of remaining elements to search through.
The space complexity of Binary Search is O(1), indicating constant space usage. The algorithm doesn't require additional memory that scales with the size of the input; it only uses a few variables to keep track of the indices and midpoints during the search.
Exploring Binary Search: A Deep Dive with Code Examples 🧑🏻‍💻
Problem 1:
Given a sorted array and a target integer value, find and return the index location of the target value.
Example:
array = [1,4,7,10,11,34,40,42]
target = 34
Technique & Approach being used:
function search(arr, target){
// Initalize pointers
// left: starts at the beginning of the array
let left = 0;
// right: starts at the end of the array
let right = arr.length - 1;
//condition: continue loop until left pointer is <= to the right pointer
while(left <= right){
// calculate the midpoint of the current search interval
let mid = Math.floor((left + right) / 2);
// if the mid point === the target value "we found the target's location"
if(arr[mid] === target){
//return the index value of the mid point
return mid
}
// otherwise if the target value is less than the midpoint value.
else if (target < arr[mid]){
//narrow the search range to the left half
right = mid -1
}
// otherwise if the target is larger than the midpoint value
else{
// narrow the search range to the right half
left = mid + 1
}
}
//if the loop completes without finding the target return -1.
return -1
}
//Time complexity: O(logn)
//Space complexity: O(1)
Problem 2:
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
function search(nums, target) {
// Initalize pointers
// left: starts at the beginning of the array
let left = 0;
// right: starts at the end of the array
let right = nums.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (nums[mid] === target) {
return mid; // Target found, return the index
}
if (nums[left] <= nums[mid]) {
// If the left part is sorted
if (nums[left] <= target && target < nums[mid]) {
// If the target is within the range of the sorted left part
right = mid - 1; // Adjust the right pointer
} else {
left = mid + 1; // Adjust the left pointer
}
} else {
// If the right part is sorted
if (nums[mid] < target && target <= nums[right]) {
// If the target is within the range of the sorted right part
left = mid + 1; // Adjust the left pointer (narrow to right half)
} else {
right = mid - 1; // Adjust the right pointer (narrow to left half)
}
}
}
return -1; // Target not found, return -1
}
// Time Complexity: O(log n)
// Space Complexity: O(1)
A short summary by Fireship:
Binary Search Algorithm in 100 Seconds - YouTube
Binary Search is an algorithm that can find the index of an element in a sorted array data structure. You've likely used Binary Search it in everyday life wi...
youtube.com
References:
Top comments (0)