Binary Search
Program for Binary Search Problem
You are given a list of unique numbers arranged in increasing order and a specific number called target.
Your task is to create a function that looks for the target in this list. If the target is found, return its position (index) in the list. If it’s not found, return -1.
The function should be efficient and complete the search in O(log n) time, meaning it should use a method like binary search that quickly narrows down the possible locations of the target.
Output: 3
Output: -1
Constraints:
- 1 <= nums.length <= 10000.
- -10000 < nums[i], target < 10000
Program for Binary Search Solution
Recommendation for Time and Space Complexity –You should aim for a solution with O(logn) time and O(1) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
Can you find an algorithm that is useful when the array is sorted? Maybe other than linear search.
Hint 2 :
The problem name is the name of the algorithm that we can use. We need to find a target value and if it does not exist in the array return -1. We have l and r as the boundaries of the segment of the array in which we are searching. Try building conditions to eliminate half of the search segment at each step. Maybe sorted nature of the array can be helpful.
There are mainly 5 approach to solve this problem-
- Recursive Binary Search Method
- Iterative Binary Search Method
- Upper Bound Method
- Lower Bound Method
- Built-in Tool Method
1. Recursive Binary Search Method
Use a recursive function to repeatedly divide the search range in half until the target is found or the range becomes empty.
- Time complexity: O(log n)
- Space complexity: O(log n)
Code
class Solution {
public:
int binary_search(int l, int r, vector<int>& nums, int target){
if (l > r) return -1;
int m = l + (r - l) / 2;
if (nums[m] == target) return m;
return ((nums[m] < target) ?
binary_search(m + 1, r, nums, target) :
binary_search(l, m - 1, nums, target));
}
int search(vector<int>& nums, int target) {
return binary_search(0, nums.size() - 1, nums, target);
}
};
public class Solution {
public int binary_search(int l, int r, int[] nums, int target) {
if (l > r) return -1;
int m = l + (r - l) / 2;
if (nums[m] == target) return m;
return (nums[m] < target) ?
binary_search(m + 1, r, nums, target) :
binary_search(l, m - 1, nums, target);
}
public int search(int[] nums, int target) {
return binary_search(0, nums.length - 1, nums, target);
}
}
class Solution:
def binary_search(self, l: int, r: int, nums: List[int], target: int) -> int:
if l > r:
return -1
m = l + (r - l) // 2
if nums[m] == target:
return m
if nums[m] < target:
return self.binary_search(m + 1, r, nums, target)
return self.binary_search(l, m - 1, nums, target)
def search(self, nums: List[int], target: int) -> int:
return self.binary_search(0, len(nums) - 1, nums, target)
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
binary_search(l, r, nums, target) {
if (l > r) return -1;
let m = l + Math.floor((r - l) / 2);
if (nums[m] === target) return m;
return (nums[m] < target) ?
this.binary_search(m + 1, r, nums, target) :
this.binary_search(l, m - 1, nums, target);
}
search(nums, target) {
return this.binary_search(0, nums.length - 1, nums, target);
}
}
2. Iterative Binary Search Method
Use a loop to perform binary search by adjusting the left and right pointers until the target is located or the search range is exhausted.
- Time complexity: O(log n)
- Space complexity: O(1)
Code
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) { int m = l + ((r - l) / 2); if (nums[m] > target) {
r = m - 1;
} else if (nums[m] < target) {
l = m + 1;
} else {
return m;
}
}
return -1;
}
};
public class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = l + ((r - l) / 2);
if (nums[m] > target) {
r = m - 1;
} else if (nums[m] < target) {
l = m + 1;
} else {
return m;
}
}
return -1;
}
}
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums) - 1
while l <= r:
# (l + r) // 2 can lead to overflow
m = l + ((r - l) // 2)
if nums[m] > target:
r = m - 1
elif nums[m] < target:
l = m + 1
else:
return m
return -1
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
search(nums, target) {
let l = 0;
let r = nums.length - 1;
while (l <= r) {
const m = l + Math.floor((r - l) / 2);
if (nums[m] > target) {
r = m - 1;
} else if (nums[m] < target) {
l = m + 1;
} else {
return m;
}
}
return -1;
}
}
3. Upper Bound Method
Find the smallest index where the target could be inserted without changing the order, focusing on the upper limit of the target’s position.
- Time complexity: O(log n)
- Space complexity: O(1)
Code
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size();
while (l < r) { int m = l + (r - l) / 2; if (nums[m] > target) {
r = m;
} else {
l = m + 1;
}
}
return (l > 0 && nums[l - 1] == target) ? l - 1 : -1;
}
};
public class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int m = l + ((r - l) / 2);
if (nums[m] > target) {
r = m;
} else {
l = m + 1;
}
}
return (l > 0 && nums[l - 1] == target) ? l - 1 : -1;
}
}
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)
while l < r:
m = l + ((r - l) // 2)
if nums[m] > target:
r = m
elif nums[m] <= target:
l = m + 1
return l - 1 if (l and nums[l - 1] == target) else -1
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
search(nums, target) {
let l = 0, r = nums.length;
while (l < r) {
let m = l + Math.floor((r - l) / 2);
if (nums[m] > target) {
r = m;
} else {
l = m + 1;
}
}
return (l > 0 && nums[l - 1] === target) ? l - 1 : -1;
}
}
4. Lower Bound Method
Find the first index where the target could appear, identifying the lower limit of its position in the sorted list.
- Time complexity: O(log n)
- Space complexity: O(1)
Code
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size();
while (l < r) { int m = l + (r - l) / 2; if (nums[m] >= target) {
r = m;
} else {
l = m + 1;
}
}
return (l < nums.size() && nums[l] == target) ? l : -1;
}
};
public class Solution {
public int search(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] >= target) {
r = m;
} else {
l = m + 1;
}
}
return (l < nums.length && nums[l] == target) ? l : -1;
}
}
class Solution:
def search(self, nums: List[int], target: int) -> int:
l, r = 0, len(nums)
while l < r:
m = l + ((r - l) // 2)
if nums[m] >= target:
r = m
elif nums[m] < target:
l = m + 1
return l if (l < len(nums) and nums[l] == target) else -1
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
search(nums, target) {
let l = 0, r = nums.length;
while (l < r) {
let m = l + Math.floor((r - l) / 2);
if (nums[m] >= target) {
r = m;
} else {
l = m + 1;
}
}
return (l < nums.length && nums[l] === target) ? l : -1;
}
}
5. Built-in Tool Method
Use built-in functions like Python’s bisect module to perform binary search efficiently with minimal code.
- Time complexity: O(log n)
- Space complexity: O(1)
Code
class Solution {
public:
int search(vector<int>& nums, int target) {
auto it = lower_bound(nums.begin(), nums.end(), target);
return (it != nums.end() && *it == target) ? it - nums.begin() : -1;
}
};
public class Solution {
public int search(int[] nums, int target) {
int index = Arrays.binarySearch(nums, target);
return index >= 0 ? index : -1;
}
}
import bisect
class Solution:
def search(self, nums: List[int], target: int) -> int:
index = bisect.bisect_left(nums, target)
return index if index < len(nums) and nums[index] == target else -1
class Solution {
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
search(nums, target) {
// There is no built in function for JS.
return nums.indexOf(target);
}
}
More Articles
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
Binary Search in Java
Binary Search in Java Programming Language
Before moving on to Binary search in Java language….let you know that it is a fundamental algorithm in computer science used to efficiently find an element in a sorted array.
Unlike linear search, which checks each element one by one, binary search divides the array into halves and eliminates one half during each iteration, significantly reducing the number of comparisons.
This article will cover the concept, implementation, time complexity, variations, and practical applications of Binary Search in Java.
So, for clear understanding of concept of Binary Search we have share the algorithm for Binary Search for Java alongwith Java code. Here’s how:
How Binary Search Works ?
- Binary search operates by repeatedly dividing the search interval in half.
- If the target value is less than the middle element, the algorithm continues the search on the left half.
- If the target value is greater, it searches the right half.
- This process continues until the target value is found or the search interval is empty.
Binary Search Algorithm: Step by Step
- Initialization: Set low = 0 and high = array.length – 1.
- Calculation of Midpoint: mid = low + (high – low) / 2
- Comparison:
- If array[mid] == target, return mid.
- If array[mid] < target, update low = mid + 1.
- If array[mid] > target, update high = mid – 1.
- Termination: The algorithm terminates when low > high or when the target value is found.
Space and Time Complexity
| Time Complexity (Best) | Ω(1) |
| Time Complexity (Avg) | Θ(log n) |
| Time Complexity (Worst) | O(log n) |
| Space Complexity | O(1) |
Edge Cases and Considerations
- Handling overflow when calculating the midpoint using low + (high – low) / 2.
- Ensuring that the array is sorted before applying binary search.
- Dealing with duplicate elements in the array.
Learn DSA
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Explaining the Binary Search Concept in Java
Methods Discussed
We will be discussing two methods for the same
- Recursive Approach
- Iterative Approach
1. Binary Search in Java (Recursive Approach)
Iterative approach uses a loop to repeatedly divide the search space in half.
It maintains
lowandhighpointers and adjusts them based on the comparison with the middle element.This approach is space efficient as it does not require additional stack space.
Advantages:
- More space efficient compared to recursion.
- Easier to debug and trace since it avoids stack overflow issues.
Disadvantages:
The logic can be slightly more complex compared to recursion due to explicit handling of the loop.
// Binary Search implimentation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{
public static int binarySearch(int array[], int left, int right, int item){
if (right >= left){
// calculation of new mid
int mid = left + (right - left)/2;
// returns position where found
if (array[mid] == item)
return mid+1;
// goes to recursive calls in left half
if (array[mid] > item)
return binarySearch(array, left, mid-1, item);
// goes to recursive calls in right half
else
return binarySearch(array, mid+1, right, item);
}
// if element is not found we return -1
else
return -1;
}
public static void main(String args[]){
int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
int item = 70;
int size = array.length;
int position = binarySearch(array, 0, size-1, item);
if(position == -1)
System.out.println("Element not found");
else
System.out.println("The value " + item + " found at position: " + position);
}
}
// Time complexity O(Log N)
Output
The value 70 found at position: 7
Space Complexity = O(log n)
Time Complexity = O(log n)
Binary Search in Java (Iterative Approach)
Let us look at the iterative approach below:
The recursive approach calls the same function with adjusted
lowandhighpointers based on the comparison.It uses the call stack to keep track of the current state, resulting in a space complexity of O(log n).
Advantages:
- Simplified logic due to inherent stack structure.
- Easier to implement and understand in terms of algorithmic flow.
Disadvantages:
- Additional space overhead due to recursive stack frames.
- Risk of stack overflow for large arrays.
// Binary Search implementation in Java (Recursive)
// Time Complexity : O(N)
// Space Complexity : O(1)
// Auxiliary Space Complexity : O(N) due to function call stack
public class Main{
public static int binarySearch(int arr[], int left, int right, int item){
while (left <= right) {
int mid = left + (right - left) / 2;
// if item is at mid
if (arr[mid] == item)
return mid;
// If item greater, ignore left half, consider only right half
if (arr[mid] < item)
left = mid + 1;
// If item is smaller, ignore right half, consider only left half
else
right = mid - 1;
}
// if we are able to reach here
// means item wasn't present
return -1;
}
public static void main(String args[]){
int[ ] array = {10, 20, 30, 40, 50, 60, 70, 80};
int item = 70;
int size = array.length;
int position = binarySearch(array, 0, size-1, item);
if(position == -1)
System.out.println("Element not found");
else
System.out.println("The value " + item + " found at position: " + position);
}
}Output
The value 70 found at position: 6
Space Complexity = O(1)
Time Complexity = O(log n)
Conclusion:
- Binary search is an efficient algorithm for finding elements in a sorted array with a time complexity of O(log n).
- The iterative approach uses constant space, while the recursive approach uses additional space due to the call stack.
- Choosing between them depends on space constraints and implementation preference.
Learn DSA
FAQ's related to Binary Search in Java
Answer:
Time complexity of binary search in Java is O(log n) in both recursive and iterative methods.
Answer:
Because each recursive call adds a new frame to the call stack, resulting in a space complexity of O(log n).
Answer:
Iterative binary search repeatedly divides the search range in half using a loop until the target is found or the range is empty.
Answer:
Iterative binary search is generally preferred due to its constant space complexity O(1) compared to O(log n) for the recursive method.
Answer:
No, binary search requires the array to be sorted in ascending order for it to work correctly.
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