Time: 2021.8.25-2021.8.30
Binary search
Binary search is also called split search. First, assume that the elements in the table are arranged in ascending order, and compare the keywords in the middle of the table with the find keywords:
1. If they are equal, the search succeeds.
2. Otherwise, use the middle position to divide the table into the first and the last two sub-tables: 1) If the key in the middle position is greater than the search key, search the previous sub-table further; 2) Otherwise, go to the next subtable.
Repeat the above process until you find a record that meets the criteria, so that the search succeeds, or until the child table does not exist, at which point the search fails.
Binary search (sort) tree
Binary Search Tree (Binary Search Tree), which is a Binary Tree with the following properties:
1. If the left subtree is not empty, the value of all nodes in the left subtree is less than or equal to the value of its root node.
2. If the right subtree is not empty, the value of all nodes in the right subtree is greater than or equal to the value of its root node.
3. The left and right subtrees are also binary sort trees.
4. Equal can occur only on one side of the left or right subtree.
Binary Sort Tree (Binary Sort Tree) : Binary Sort Tree
The binary lookup tree inserts nodes
Insert a node into the binary search tree with node as the root:
If the value of insert _node is less than the value of the current node: If the node has a left subtree, the node is recursively inserted into the root binary sort tree. Otherwise, assign node->left to the node address.
Otherwise (greater than or equal to): If node has a right subtree, recursively insert the node into the root binary sort tree with the right subtree. Otherwise, assign node->right to the node address.
The binary lookup tree looks up values
Whether the lookup value value appears in the binary lookup tree:
If value is equal to the value of the node being viewed: returns true.
If the value of the value is less than the value of the current node: If the current node has a left subtree, continue to look for the value in the left subtree. Otherwise, return false.
Otherwise (the value of the node is greater than the value of the current node): If the current node has a right subtree, continue to look for the value in the right subtree; Otherwise, return false.
1. LeetCode35 searches for insert location
class Solution {
public int searchInsert(int[] nums, int target) {
int index = -1;// Finally returns the subscript
int begin = 0;// Search the left endpoint of the interval
int end = nums.length-1;// Search the right endpoint of the interval
while(index == -1) {int mid = (begin+end)/2;
if(target == nums[mid]){
index = mid;
}
else if(target < nums[mid]){
if(mid == 0||target > nums[mid-1]){
index = mid;
}
end = mid-1;// If target is less than the midpoint, the right endpoint of the interval is updated
}
else if(target > nums[mid]){
if(mid == nums.length-1||target < nums[mid+1]){
index = mid+1;
}
begin = mid+1;// If target is greater than the midpoint, the left endpoint of the interval is updated}}returnindex; }}Copy the codeLeetCode34 looks for the first and last positions of elements in the sorted array
If target == nums[mid], mid == 0 or nums[mid-1] < target, mid == 0 or nums[mid-1] < target, mid == 0; Otherwise, set the right end of the interval to mid-1. If target == nums[mid], mid == nums.size() -1 or nums[mid + 1]>target, mid is the right endpoint of the interval. Otherwise, set the left end of the interval to mid + 1.
class Solution {
public int[] searchRange(int[] nums, int target) {
int leftIdx = left_bound(nums, target);
int rightIdx = right_bound(nums, target);
if (leftIdx <= rightIdx && rightIdx < nums.length) {
return new int[]{leftIdx, rightIdx};
}
return new int[] {-1, -1};
}
public int left_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]){
if (mid == 0||nums[mid-1] < target){
return mid;
}
right = mid - 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target){
left = mid + 1; }}return -1;
}
public int right_bound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (target == nums[mid]){
if (mid == nums.length - 1||nums[mid+1] > target){
return mid;
}
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] < target){
left = mid + 1; }}return -1; }}Copy the code3. LeetCode33 searches rotated sorted arrays
Thinking: nums (begin) > nums [end]
class Solution {
public int search(int[] nums, int target) {
int begin = 0,end = nums.length-1;
while(begin <= end){
int mid = (begin+end)/2;
if(target == nums[mid]){
return mid;
}
else if(target < nums[mid]){
if(nums[begin] < nums[mid]){
if(target >= nums[begin]){
end = mid-1;
}else{
begin = mid+1; }}else if(nums[begin] > nums[mid]){
end = mid-1;
}else if(nums[begin] == nums[mid]){
begin = mid+1; }}else if(target > nums[mid]){
if(nums[begin] < nums[mid]){
begin = mid+1;
}else if(nums[begin] > nums[mid]){
if(target >= nums[begin]){
end = mid-1;
}else{
begin = mid+1; }}else if(nums[begin] == nums[mid]){
begin = mid+1; }}}return -1; }}Copy the codeLeetcode official solution
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if (n == 0) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1; }}else {
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1; }}}return -1; }}Copy the code4. LeetCode449 serializes and deserializes binary search trees
The binary search tree is encoded as a string: the binary search tree is traversed before the sequence, traversing the integer data into a string, and these string data are connected, the connection is separated by special symbols.
Decode the string into a binary search tree: split the string one by one according to the delimiter “#” during encoding, and build the first number as the root node of the binary search tree. Insert the nodes constructed by the following numbers into the root node according to the sequence of parsing, and return to the root node, that is, complete the decoding work.
LeetCode Comment code
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; }} * * /
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root == null) {
return "";
}
StringBuilder sb = new StringBuilder();
BST_preorder(root, sb);// Convert the tree pointed to by root to the string sb
return sb.substring(0, sb.length() -1);
}
Root. val is converted to a string and stored in sb
private void BST_preorder(TreeNode root, StringBuilder sb) {
if (root == null) {
return;
}
sb.append(root.val).append("#");
BST_preorder(root.left, sb);
BST_preorder(root.right, sb);
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if (data.isEmpty()) {
return null;
}
String[] split = data.split("#");
return buildTreeNode(split, 0, split.length -1);
}
private static TreeNode buildTreeNode(String[] split, int left, int right) {
if (left > right) {
return null;
}
TreeNode root = new TreeNode(Integer.parseInt(split[left]));
int index = right + 1;
for (int i = left + 1; i <= right; i++) {
if (Integer.parseInt(split[i]) > root.val) {
index = i;
break;
}
}
root.left = buildTreeNode(split, left + 1, index -1);
root.right = buildTreeNode(split, index, right);
returnroot; }}// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// String tree = ser.serialize(root);
// TreeNode ans = deser.deserialize(tree);
// return ans;
Copy the code