二分查找（模版）

Fsgojy / 2024-07-12 / 原文

二分查找(手写模版)

模版1: 大部分情况下的最好模版

例如：int[] nums = {0, 15, 25, 30 ,30, 50 };

注：数据的存储从1索引开始，0索引处不存储数据

查找返回最后一个符合条件的数的下标

int find(int q){
  int l =0,r = nums.length; // l 和 r 均为开区间
  while(l+1<r){
    int mid = l+r>>1;
    if(nums[mid]<=q)
      l = mid;
    else
      r = mid;
  }
  return l;
}

查找返回第一个符合条件的数的下标

int find(int q){
  int l =0, r=nums.length; // l 和 r 均为开区间
  while(l+1<r){
    int mid = l+r>>1;
    if(nums[mid]>=q)
      r = mid;
    else
      l = mid;
  }
  return r;
}

模版2: 当模版1用不了时，用该模版

情况描述：当nums的存储规则是题目规定的，要求数组存储数据必须从0开始，如leetcode，不能用模版1

例如：int[] nums = {15, 25, 30 ,30, 50}

注：数据的存储从0索引开始

查找返回最后一个符合条件的下标

int find(int q){
  int l = 0, r = nums.length-1;  //l 和 r 均为闭区间
  while(l<=r){
    int mid = l+r>>1;
    if(nums[mid]<=q)
      l = mid+1;
    else
      r = mid-1;
  }
  return l;
}

查找返回第一个符合条件的下标

int find(int q){
  int l = 0, r = nums.length-1; //l 和 r 均为闭区间
  while(l<=r){
    int mid = l+r>>1;
    if(nums[mid]>=q)
      r = mid-1;
    else
      l = mid+1;
  }
  return r;
}