二分搜索【模板】

1、基本的二分搜索

public int binary_search(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){
       right = mid - 1;
     }else if (nums[mid] < right){
       left = mid + 1;
     }
   }
   return -1;
}

2、寻找左侧边界的二分搜索

public int left_bound(int[] nums, int target) {
   if (nums.length == 0) {
     return -1;
   }
   int left = 0;
   int right = nums.length;
   while (left < right) {
     int mid = left + (right - left) / 2;
     if (nums[mid] == target) {
       right = mid;
     } else if (nums[mid] > target) {
       right = mid;
     } else if (nums[mid] < target) {
       left = mid + 1;
     }
   }
   if (left == nums.length) {
     return -1;
   }
   return nums[left] == target ? left : -1;
 }

3、寻找右侧边界的二分搜索

public int right_bound(int[] nums, int target) {
   if (nums.length == 0) {
     return -1;
   }
   int left = 0;
   int right = nums.length;
   while (left < right) {
     int mid = left + (right - left) / 2;
     if (nums[mid] == target) {
       left = mid + 1;
     } else if (nums[mid] > target) {
       right = mid;
     } else if (nums[mid] < target) {
       left = mid + 1;
     }
   }
   if (left == 0) {
     return -1;
   }
   return nums[left - 1] == target ? (left - 1) : -1;
 }