#Binary Search:
Binary Search
Intuition:
Binary search is an efficient algorithm to find a target value within a sorted array. It works on the idea of repeatedly dividing the search space(the space in which the search of the target is taking place) in half until the target is found or it is concluded that the target is not present in the array.
What is Search Space?
The target must be found in the array itself. This means that the space in which the target must be searched for is the array. Now, to mark the search space, two pointers will come in hand -
Low:A pointer pointing to the smallest index possible of the search space.High:A pointer pointing to the greatest index possible of the search space.
Initially, the search space is the whole array, i.e., the low and high pointers will be initialized with the following values:low = 0, high = n-1(where n is the size of the array)
Understanding:
To find the target, the middle element of the current search space will be found. If it matches the target, the search ends. Otherwise
If the middle element is less than the target: All the elements to the left of the middle element will also be less than the target (because the array is sorted). Thus, the search space can be trimmed down to the right half discarding the left half.
If the middle element is greater than the target: All the elements to the right of the middle element will also be greater than the target (because the array is sorted). Thus, the search space can be trimmed down to the left half discarding the right half.
This way, the search space is divided in half with every search increasing the chances of finding the target.
Edge Case:
If the target is not present in the array, the search space will eventually reduce to zero with every search indicating the absence of target in the given array. In such cases, -1 can be returned.
Approach:
Two pointers are set up to define the search space — one pointing to the beginning of the array and the other to the end.
The middle element of the current search space is found and the search space is repeatedly divided in half:
If the middle element matches the target, the index is returned.
If the target is greater than the middle element, the search space is narrowed to the right half.
If the target is smaller, the search space is narrowed to the left half.
If the loop ends without finding the target, return -1 indicating that the target is not present in the array.
In Humanised Language:
Two pointers are used: the first is the low pointer and the second is the high pointer. The low pointer points to the starting index, and the high pointer points to the last index of the array. Then calculatemid = low + (high - low) / 2.
Compare arr[mid] with your target. If arr[mid] == target, return that index. Otherwise, check whether the target is greater than the mid value. If yes, trim the search space and move to the second half of the array. If not, move to the first half of the array.
This process repeats until the target is found or it is concluded that the target is not present in the array. In that case, return -1.
Below are solutions in multiple programming languages.
You can follow the one that matches your preferred language.
Solution:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Function to find the given target in a sorted array
int search(vector<int>& nums, int target) {
int n = nums.size(); // Size of array
// Pointers to define the search space
int low = 0, high = n-1;
// Until the search space is not empty
while (low <= high) {
// Find the middle element
int mid = (low + high) / 2;
// If it matches the target
if (nums[mid] == target)
return mid;
// If the target is greater than middle element
else if (target > nums[mid])
low = mid + 1;
// Otherwise
else
high = mid - 1;
}
// If the target is not found
return -1;
}
};
int main() {
vector<int> a = {-1, 0, 3, 5, 9, 12};
int target = 9;
// Creating an instance of Solution class
Solution sol;
// Function call to find the given target in a sorted array
int ind = sol.search(a, target);
if(ind == -1)
cout << "The target is not present." << endl;
else
cout << "The target is at index: " << ind << endl;
return 0;
}#include <stdio.h>
int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == key)
return mid; // element found
else if (arr[mid] < key)
low = mid + 1; // search right half
else
high = mid - 1; // search left half
}
return -1; // element not found
}
int main() {
int arr[] = {2, 4, 6, 8, 10, 12, 14};
int n = sizeof(arr) / sizeof(arr[0]);
int key = 10;
int result = binarySearch(arr, n, key);
if (result != -1)
printf("Element found at index %d\n", result);
else
printf("Element not found\n");
return 0;
}
class Solution:
# Function to find the given target in a sorted array
def search(self, nums, target):
n = len(nums) # Size of array
# Pointers to define the search space
low, high = 0, n - 1
# Until the search space is not empty
while low <= high:
# Find the middle element
mid = (low + high) // 2
# If it matches the target
if nums[mid] == target:
return mid
# If the target is greater than middle element
elif target > nums[mid]:
low = mid + 1
# Otherwise
else:
high = mid - 1
# If the target is not found
return -1
# Creating an instance of Solution class
sol = Solution()
# Test the function
a = [-1, 0, 3, 5, 9, 12]
target = 9
# Function call to find the given target in a sorted array
ind = sol.search(a, target)
if ind == -1:
print("The target is not present.")
else:
print("The target is at index:", ind)class Solution {
// Function to find the given target in a sorted array
search(nums, target) {
let n = nums.length; // Size of array
// Pointers to define the search space
let low = 0, high = n - 1;
// Until the search space is not empty
while (low <= high) {
// Find the middle element
let mid = Math.floor((low + high) / 2);
// If it matches the target
if (nums[mid] === target)
return mid;
// If the target is greater than middle element
else if (target > nums[mid])
low = mid + 1;
// Otherwise
else
high = mid - 1;
}
// If the target is not found
return -1;
}
}
// Creating an instance of Solution class
let sol = new Solution();
// Test the function
let a = [-1, 0, 3, 5, 9, 12];
let target = 9;
// Function call to find the given target in a sorted array
let ind = sol.search(a, target);
if (ind === -1)
console.log("The target is not present.");
else
console.log("The target is at index: " + ind);using System;
public class Solution
{
// Function to find the given target in a sorted array
public int search(int[] nums, int target)
{
int n = nums.Length; // Size of array
// Pointers to define the search space
int low = 0, high = n - 1;
// Until the search space is not empty
while (low <= high)
{
// Find the middle element
int mid = low + (high - low) / 2;
// If it matches the target
if (nums[mid] == target)
return mid;
// If the target is greater than middle element
else if (target > nums[mid])
low = mid + 1;
// Otherwise
else
high = mid - 1;
}
// If the target is not found
return -1;
}
public static void Main(string[] args)
{
// Creating an instance of Solution class
Solution sol = new Solution();
// Test the function
int[] a = { -1, 0, 3, 5, 9, 12 };
int target = 9;
// Function call to find the given target in a sorted array
int ind = sol.search(a, target);
if (ind == -1)
Console.WriteLine("The target is not present.");
else
Console.WriteLine("The target is at index: " + ind);
}
}package main
import "fmt"
// search finds the target in a sorted slice, returning its index or -1
func search(nums []int, target int) int {
low, high := 0, len(nums)-1 // Pointers to define the search space
for low <= high {
mid := (low + high) / 2 // Find the middle element
if nums[mid] == target {
return mid // If it matches the target
} else if target > nums[mid] {
low = mid + 1 // Search the right half
} else {
high = mid - 1 // Search the left half
}
}
return -1 // If the target is not found
}
func main() {
a := []int{-1, 0, 3, 5, 9, 12}
target := 9
ind := search(a, target)
if ind == -1 {
fmt.Println("The target is not present.")
} else {
fmt.Printf("The target is at index: %d\n", ind)
}
}
Complexity Analysis:
Time Complexity: O(log(N)) (where N is the size of the given array)
In each step, the search space is divided into two halves. In the worst case, this process will continue until the search space can no longer be divided and the number of divisions required to reduce the array size to one is log(N), making the overall time complexity O(log(N)).
Space Complexity: O(1):
Using only a couple of variables.