Search Flashcards
What is the base case for binary search (iterative and recursive)?
Base:
if(right <= left)
How do we know we have one element left in binary search?
left == right
What is binary search?
Binary search is an algorithm that outlines how to find something in an ordered list
How does binary search work?
Repeatedly halving the area we search between by checking if the midpoint is less than or greater than the target and updating the left or right pointers accordingly
What is the time complexity of Binary Search?
O(log n) because we half the area we search within each time
This makes it an efficient algorithm for search large data sets
What are the two ways you can implement Binary Search in Java?
- Recursion
- Iterative
What do you do binary search on?
A sorted list
ie.,
integers ordered by their intrinsic value
financial transactions ordered by the transaction time
Describe the recursive approach to implementing binary search?
- Base case: if(right < left) return -1
- int middle = (left + right) / 2
- if(array[middle] == target) return middle
- if(target < array[middle]) return method(array, target, left, middle-1)
- if(target > array[middle] return method(array, target, middle+1, right)
Describe the iterative approach to implementing binary search?
- while(left <= right)
- int middle = (left + right) / 2
- if(array[middle] == target) return middle
- if(target < array[middle]) right = middle - 1;
- else the target is in the right so we update the left pointer: left = middle + 1
What algorithm would be best to find the position of a target value within a SORTED array?
Binary Search
Write the method for a recursive approach to Binary Search?
public int binarySearchRec(int[] arr, int target, int left, int right){
int mid = (left + right)/2;
if(right<left) return -1;
if(arr[mid] == target) {
return mid;
} else if(target < arr[mid]) {
return binarySearchRec(arr, target, left, mid - 1);
} else {
return binarySearchRec(arr, target, mid+1, right);
}
}
Write the method for the iterative approach to Binary Search
public static int bsIterative(int[] array, int target){
int left = 0;
int right = array.length - 1;
while(left <= right){
int middle = (left + right)/2;
if(array[middle] == target){
return middle;
} else if(target < array[middle]){
right = middle-1;
} else {
left = middle+1;
}
}
return -1;
}
Describe how you invert a binary tree?
We can use recursion to invert a Binary tree
Start with the root node, traverse the left subtree and once you get to the bottom swap, then repeat for the right subtree
Repeat for the next level up in the tree
Describe how binary tree:
—-4—-
–2–7–
1-3-6-9-
Can be inverted to:
—-4—-
–7–2–
9-6-3-1
Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
Use recursion to traverse down the subtrees swapping the left and right.
public TreeNode invertTree(TreeNode root) {
// base case
if (root == null){
return null;
}
TreeNode right = invertTree(root.right);
TreeNode left = invertTree(root.left);
// swap
root.left = right;
root.right = left;
return root;
}
Traverse down 1 side
root = 4, left = 2
root = 2, left = 1, right = 3
root = 1, left = nothing, right = nothing
// now it will move to the next step because there isn't anything left
left = 3 (right)
right 1 (left)
Traverse down next side
root = 4, right = 7
root = 7, left = 6, right = 9
root = 9, left = nothing, right = nothing
// now will
move the next step because isn't anything left
left = 9, right = 6
Now we have finished the bottom layer, we swap the sub trees
What is the space complexity of the iterative approach to binary search?
O(1) constant time
