中英文企业网站系统,深圳网站建设公司麦,重庆市建设工程施工安全管理总站,中国十大门户类网站前言 前些天我做了一道题目#xff0c;题目中要求使用二分查找#xff0c;我便按照我心中的二分查找#xff0c;信心满满的提交上去了。结果发现无限循环#xff0c;后面我便去查阅了资料 二分查找的条件 用于查找的内容需要是有序的查找的数量只能是一个 二分查找的二种方…前言 前些天我做了一道题目题目中要求使用二分查找我便按照我心中的二分查找信心满满的提交上去了。结果发现无限循环后面我便去查阅了资料 二分查找的条件 用于查找的内容需要是有序的查找的数量只能是一个 二分查找的二种方法 左闭右闭左闭右开 二种用法区别就在于 while循环中 left 和 right 的关系到底是 left right 还是 left right迭代过程中 middle 和 right 的关系到底是 right mid - 1 还是 right mid
1. 左闭右闭
左闭右闭每次查找的区间在[left, right]因为定义 target 在[left, right]区间所以
循环条件要使用while(left right)因为当 left right 这种情况发生的时候得到的结果是有意义的if(arr[mid] target) right 要赋值为 mid - 1 因为当前的 arr[mid] 一定不是 target ,那么接下来需要查找范围就是[left, mid - 1]
int search(int arr[], int size, int target) //size是数组的大小target是需要查找的值
{int left 0;int right size - 1; // 定义了target在左闭右闭的区间内[left, right]while (left right) //当left right时区间[left, right]仍然有效{ int mid left ((right - left) / 2);//等同于 (left right) / 2防止溢出if (arr[mid] target) {right mid - 1; //target在左区间所以[left, mid - 1]}else if (arr[mid] target) {left mid 1; //target在右区间所以[mid 1, right]}else { //既不在左边也不在右边那就是找到答案了return mid;}}//没有找到目标值return -1;
} 2.左闭右开
左闭右开每次查找的区间在 [left, right),条件控制应该如下
循环条件使用while (left right)if (arr[mid] target) right mid因为当前的 arr[middle] 是大于 target 的不符合条件,不能取到 mid并且区间的定义是 [left, right)刚好区间上的定义就取不到 right, 所以 right 赋值为 mid。
int search(int arr[], int size, int target) //size是数组的大小target是需要查找的值
{int left 0;int right size; while (left right) { int mid left ((right - left) / 2);//等同于 (left right) / 2防止溢出if (arr[mid] target) {right mid; //target在左区间所以[left, mid)}else if (arr[mid] target) {left mid 1; //target在右区间所以[mid 1, right)}else { //既不在左边也不在右边那就是找到答案了return mid;}}//没有找到目标值return -1;
} 这二种方法必须匹配使用循环条件和后续的区间赋值
