STL之二分查找

binary_search进行二分查找

• 在从小到大排好序的基本类型数组上进行二分查找

  ​ binary_search(数组名+n1,数组名+n2,值);

  ​ n1和n2都是int类型的表达式，可以包含变量

  ​ 如果n1=0，则+n1可以不写

  查找区间为下标范围为[n1,n2)的元素，下标为n2的元素不在查找区间内

  在该查找区间内查找“等于”值的元素，返回值为true（找到）或false（没找到）

  “等于”的含义：a等于b <=> a<b和b<a都不成立

• 在用自定义排序规则排好序的，元素为任意的T类型的数组中进行二分查找

  ​ binary_search(数组名+n1,数组名+n2,值,排序规则结构名());

  ​ n1和n2都是int类型的表达式，可以包含变量

  ​ 如果n1=0，则+n1可以不写

  查找区间为下标范围为[n1,n2)的元素，下标为n2的元素不在查找区间内

  在该查找区间内查找“等于”值的元素，返回值为true（找到）或false（没找到）

  查找时的排序规则，必须和排序时的规则一致
  “等于”的含义：a等于b <=> a<b和b<a都不成立

lower_bound二分查找下界

• 在对元素类型为T的从小到大排好序的基本类型数组上进行二分查找
  ​ T * lower_bound(数组名+n1,数组名+n2,值);
  返回一个指针 T * p;
  *p是查找区间里下标最小的，大于等于“值”的元素。如果找不到，p指向下标为n2的元素

• 在元素为任意的T类型、按自定义排序规则排好序的数组中进行查找
  ​ T * lower_bound(数组名+n1,数组名+n2,值,排序规则结构名());
  返回一个指针 T * p;
  *p是查找区间里下标最小的，按自定义排序规则，可以排在“值”后面的元素。如果找不到，p指向下标为n2的元素

upper_bound二分查找下界

• 在对元素类型为T的从小到大排好序的基本类型数组上进行二分查找
  ​ T * upper_bound(数组名+n1,数组名+n2,值);
  返回一个指针 T * p;
  *p是查找区间里下标最小的，大于“值”的元素。如果找不到，p指向下标为n2的元素

• 在元素为任意的T类型、按自定义排序规则排好序的数组中进行查找
  ​ T * upper_bound(数组名+n1,数组名+n2,值,排序规则结构名());
  返回一个指针 T * p;
  *p是查找区间里下标最小的，按自定义排序规则，一定排在“值”后面的元素。如果找不到，p指向下标为n2的元素