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);
}
}
