二分查找_牛客博客

一：二分查找定义：

二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。 ——百度百科

二：二分查找基本操作：

1、找到该值在数组中的下标

inline int find1(int *a, int x) {
  int l=1,r=n;
  while(l<=r) {
    int mid=(l+r)>>1;
    if(a[mid]==x) return mid;
    else if(a[mid]<x) l=mid+1;
    else r=mid-1;
  }
  return -1;
}

2、查找第一个与\(x\)相等的元素在数组中下标

inline int find2(int *a, int x) {。 
  int l=1,r=n;
  while(l<=r) {
    int mid=(l+r)>>1;
    if(a[mid]>=x) r=mid-1;
    else l=mid+1;
    if(l<=n&&a[l]==x) return l;
  }
  return -1;
}

3、查找最后一个与\(x\)相等的元素在数组中下标

inline int find3(int *a, int x) { 
  int l=1,r=n;
  while(l<=r) {
    int mid=(l+r)>>1;
    if(a[mid]<=x) l=mid+1;
    else r=mid-1;
    if(r>=1&&a[r]==x) return r; 
  } 
  return -1;
}

4、查找最后一个小于\(x\)的元素下标

inline int find4(int *a,int x) { 
  int l=1,r=n;
  while(l<=r) {
    int mid=(l+r)>>1;
    if(a[mid]>=x) r=mid-1;
    else l=mid+1;
  }
  return r;
} 
//查找最后一个小于x的元素，也就是说返回小于x的最右边元素下标。

5、查找第一个大于等于\(x\)的元素下标

inline int find5(int *a,int x) { 
  int l=1,r=n;
  while(l<=r) {
    int mid=(l+r)>>1;
    if(a[mid]>=x) r=mid-1;
    else l=mid+1;
  } 
  return l;
}
//查找第一个等于或者大于x的元素，也就是说等于查找x值的元素有好多个
//返回这些元素最左边元素下标如果没有等于x值的元素，则返回大于x的最左边元素下标。

6、查找第一个大于\(x\)的元素下标

inline int find6(int *a,int x) {
  int l=1,r=n;
  while(l<=r) {
    int mid=(l+r)>>1;
    if(a[mid]>x) r=mid-1;
    else l=mid+1;
  }
  return l;
}

二分查找