When to use: Used for searching for an element in a sorted list or array. Reduces the time complexity from O(n) to O(log n).
Conditions:
Input must be sorted.
Steps:
- Set the left index = 0, right index = length - 1.
- Get middle index: (left - right) / 2. Make sure that middle index is inside the iteration so it can change and calculate for every left and right index.
- Check if middle element is equal to the target, if it is return and end search.
- If middle element is less than target, search right side of the list. Set the left index to be at the middle + 1.
- If middle element is greater than target, search left side of the list. Set the right index to be at the middle - 1.
- Iterate until match is found or left index is greater than right index.
Two Types of Approach: Recursive and Iterative
Recursive Approach:
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length -1;
return binarySearch(nums, target, left, right);
}
public int binarySearch(int[] nums, int target, int left, int right){
int middle = (right + left) / 2;
if(right < left){
return -1;
}
if(target == nums[middle]){
return middle;
}
if(target < nums[middle]){
return binarySearch(nums, target, left, middle - 1);
} else {
return binarySearch(nums, target, middle + 1, right);
}
}
}
Iterative Approach:
class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length -1;
while (right >= left){
int middle = (right + left) / 2;
if(target == nums[middle]){
return middle;
}
if(target < nums[middle]){
right = middle - 1;
} else {
left = middle + 1;
}
}
return -1;
}
}
Top comments (0)