二分查找模板

二分查找及其变形模板

基本二分查找

public int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1;

    while(left <= right) {
        int mid = (right - left) / 2 + left;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1;
        else if (nums[mid] > target)
            right = mid - 1;
    }
    return -1;
}

二分查找左边界

public int searchLeftBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int index = -1;
    while (left <= right) {
      int mid = (right - left) / 2 + left;
      if (nums[mid] == target) {
        index = mid; // 记录位置
        right = mid - 1; //继续向左尝试
      } else if (nums[mid] > target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return index;
}

二分查找右边界

public int searchRightBound(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int index = -1;
    while (left <= right) {
      int mid = (right - left) / 2 + left;
      if (nums[mid] == target) {
        index = mid; // 记录位置
        left = mid + 1; //继续向右尝试
      } else if (nums[mid] > target) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }
    return index;
}

二分查找小于target的最大元素

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

二分查找大于target的最小元素

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