再看二分查找
-
最基本的二分查找
int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 1; // 注意 while(left <= right) { int mid = left + (right - left) / 2; //注意 if(nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; } return -1; }
寻找左侧边界的二分查找——查找有多少个数小于目标数
int leftBound(int[] nums,int target) { int left = 0; int right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid-1; } } if(left>=nums.length || nums[left+1]!=target){ return -1; } return left; }
寻找右侧边界的二分查找
int rightBound(int[] nums, int target) { int left = 0; int right = nums.length-1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] > target) { right = mid-1; } else { left = mid+1; } } if(right<0 || nums[right]!=target){ return -1; } return nums.length-1-right; }
-
-
太棒了,向你学习