1. 寻找特定target

如果right = nums.length - 1，此时查找区间为两端都闭[left, right], 则while循环条件应为left <= right，即left > right时停止查找

public int binarySearch(int[] nums, int target) {
  int left = 0;
	int right = nums.length - 1;
  while(left <= right) {
    int middle = (right - left) / 2 + left;
    if(nums[middle] == target) {
      return middle;
    } else if(nums[middle] > target) {
      right = middle - 1;
    } else if(nums[middle] < target) {
      left = middle + 1;
    }
  }
  
  //不存在
  return -1;
}

2. 寻找下界

nums[middle] == target时应该向下逼近，即right = middle - 1

public int lowerBound(int[] nums, int target) {
  int left = 0;
	int right = nums.length - 1;
  //[left, right]
  while(left <= right) {
    int middle = (right - left) / 2 + left;
    if(nums[middle] == target) {
      //[left, middle - 1]
      right = middle - 1
    } else if(nums[middle] > target) {
      //[left, middle - 1]
      right = middle - 1;
    } else if(nums[middle] < target) {
      //[middle + 1, right]
      left = middle + 1;
    }
  }
  
  //不存在
  if(left >= nums.length || nums[left] != target) {
    return -1;
  }
  return left;
}

3. 寻找上界

nums[middle] == target时应该向上逼近，即left = middle - 1

public int upperBound(int[] nums, int target) {
  int left = 0;
	int right = nums.length - 1;
  //[left, right]
  while(left <= right) {
    int middle = (right - left) / 2 + left;
    if(nums[middle] == target) {
      //[middle - 1, right]
      left = middle - 1
    } else if(nums[middle] > target) {
      //[left, middle - 1]
      right = middle - 1;
    } else if(nums[middle] < target) {
      //[middle + 1, right]
      left = middle + 1;
    }
  }
  
  //不存在
  if(right < 0 || nums[right] != target) {
    return -1;
  }
  return left;
}

二分查找

Effy

1. 寻找特定target

2. 寻找下界

3. 寻找上界

Other Articles

背包问题

garbageCollect