Algorithm: Binary Search
Published:
notes about solving tree-related coding questions
1. Core code block
There are two ways to write a binary search: (1)while loop, (2)recursion
1(1). Use a while loop
// using Java
int binarySearch(int[] a, int x){
int low=0;
int high=a.length -1;
int mid;
while(low <= high){
mid = low + (high-low)/2
if(a[mid] == x){
return mid;
}
else if(a[mid] < x){
low = mid+1;
}
else{
high = mid-1;
}
}
return -1;
}
# using python
def binarySearch(a: List[int], x: int) -> int:
low = 0
high = len(a)-1
# Using while loop
while(low <= high):
mid = low + (high-low)/2
# stop criteria:
if a[mid] == x:
return mid
elif a[mid] < x:
low = mid+1
else:
high = mid-1
return -1 # Error
1(2). Use recursion
// use Java
int binarySearch(int[] a, int x, int low, int high){
if (low > high) {return -1;}
int mid = low + (high-low)/2;
if (a[mid]==x){return mid;}
else if (a[mid] < x){return binarySearch(a, x, mid+1, high);}
else {return binarySearch(a, x, low, mid-1);}
}
def binarySearch(a: List[int], x: int, low: int, high: int) -> int:
if low > high: return -1
mid = low + (high-low)/2
if a[mid]==x:
return mid
elif a[mid]<x:
return binarySearch(a, x, mid+1, high)
else:
return binarySearch(a, x, low, mid-1)
2. Leetcode questions (sorted by frequency, then difficulty)
There will be 3 different levels of mastery:
- Unvisited: Not done
- Forgotten: Not remember
- Familiar: Remember the overall structure
- Master: Bug-free and remember all the pitfalls
4(1). High Frequency
| Question | Mastery | Core coding skills | Pitfalls | Last date of practice |
|---|---|---|---|---|
| 4 Median of Two Sorted Arrays | Familiar | 用较快时间(log)求数组中位数 | 1. need to find the location of partitionX and partitionY, and partitionX + partitionY = (X+Y+1)/2. 2. stop condition is that maxLeftX < minRightY and maxLeftY < minRightX. 3. to choose the 1st partition index, we only binary search the shorter array, and we always assume the 1st input is shorter(achieved it by if and flip). 4. The overall structure for binarySearch is a while loop, while low<=high. 5. be careful the edge cases where there are empty sub arrays, in those cases, we let min/max to be inf. 6. be careful based on the conditions, we only modify and low, or high, not both of them(as the other one may be modified in the previous iteration) | 08/12/2021 |
| 987 Vertical Order Traversal of a Binary Tree | Unvisited | ??? | ??? | 06/15/2021 |
| 98 Validate Binary Search Tree | Unvisited | ??? | ??? | 06/15/2021 |
| 103 Binary Tree Zigzag Level Order Traversal | Unvisited | ??? | ??? | 06/15/2021 |
| 226 Invert Binary Tree | Unvisited | ??? | ??? | 06/15/2021 |
| 426 Convert Binary Search Tree to Sorted Doubly Linked List | Unvisited | ??? | ??? | 06/15/2021 |
| 173 Binary Search Tree Iterator | Unvisited | ??? | ??? | 06/15/2021 |
| 1650 Lowest Common Ancestor of a Binary Tree III | Unvisited | ??? | ??? | 06/15/2021 |
| 545 Boundary of Binary Tree | Unvisited | ??? | ??? | 06/15/2021 |