算法——二分查找

1、在有序数组中查找元素的第一个和最后一个位置

 1 class Solution {
 2     public int[] searchRange(int[] nums, int target) {
 3         int leftindex=binarySearch(nums,target);
 4         int rightindex=binarySearch(nums,target+1)-1;
 5         if(leftindex==nums.length||nums[leftindex]!=target||nums[rightindex]!=target){
 6             return new int[]{-1,-1};
 7         }
 8         return new int[]{leftindex,rightindex};
 9 
10 
11     }
12     int binarySearch(int[] nums,int target){
13         int left=0;
14         int right=nums.length-1;
15         while(left<=right){
16             int mid=left+(right-left)/2;
17             if(nums[mid]<target){
18                 left=mid+1;
19             }else{
20                 right=mid-1;
21             }
22         }
23         return left;
24 
25     }
26 }

2、x的平方根

 1 class Solution {
 2     public int mySqrt(int x) {
 3         int left = 0;
 4         int right = x;
 5         int ans = 0;
 6         while(left <= right){
 7             int mid = left + (right - left) / 2;
 8             if((long)mid * mid <= x){
 9                 ans = mid;
10                 left = mid + 1;
11             }else{
12                 right = mid - 1;
13             }
14         }
15         return ans;
16     }
17 }

3、搜索二维数组

 1 class Solution {
 2     public boolean searchMatrix(int[][] matrix, int target) {
 3         int i=0;
 4         int j=j=matrix[0].length-1;
 5         while(i<matrix.length&&j>=0){
 6             if(target==matrix[i][j])return true;
 7             else{
 8             if(target>matrix[i][j]){
 9                 i++;
10             }
11             else if(target<matrix[i][j]){
12                 j--;
13             }
14             }
15             
16         }
17         return false;
18 
19     }
20 }

4、完全二叉树的节点个数

 1 class Solution {
 2     public int countNodes(TreeNode root) {
 3         if (root == null) {
 4             return 0;
 5         }
 6         int level = 0;
 7         TreeNode node = root;
 8         while (node.left != null) {
 9             level++;
10             node = node.left;
11         }
12         int low = 1 << level, high = (1 << (level + 1)) - 1;
13         while (low < high) {
14             int mid = (high - low + 1) / 2 + low;
15             if (exists(root, level, mid)) {
16                 low = mid;
17             } else {
18                 high = mid - 1;
19             }
20         }
21         return low;
22     }
23 
24     public boolean exists(TreeNode root, int level, int k) {
25         int bits = 1 << (level - 1);
26         TreeNode node = root;
27         while (node != null && bits > 0) {
28             if ((bits & k) == 0) {
29                 node = node.left;
30             } else {
31                 node = node.right;
32             }
33             bits >>= 1;
34         }
35         return node != null;
36     }
37 }

class Solution {
    public int countNodes(TreeNode root) {
    	if(root == null) {
    		return 0;
    	}
    	int left = countNodes(root.left);
    	int right = countNodes(root.right);
    	
    	return left+right+1;
    	
    }
}