模板:(通用模板,推荐)
给定一个排序的整数数组(升序)和一个要查找的整数target
,用O(logn)
的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1
。
int binarySearch(vector<int> &array, int target) { if (array.size() == 0) { return -1; } int start = 0; int end = array.size() - 1; int mid; while (start + 1 < end) { mid = start + (end - start) / 2; if (array[mid] == target) { end = mid; } else if (array[mid] < target){ start = mid; } else if (array[mid] > target) { end = mid; } } if (array[start] == target) { return start; } else if (array[end] == target) { return end; } return -1; }
若将条件改为查找target最后一次出现的下标(从0开始),那么程序将发生改变,循环中如果 array[mid] = target, 则 start = mid; 且最后的边界判断改为先判断
array[end] == target; 其他不变。
int binarySearch(vector<int> &array, int target) { if (array.size() == 0) { return -1; } int start = 0; int end = array.size() - 1; int mid; while (start + 1 < end) { mid = start + (end - start) / 2; if (array[mid] <= target) { start = mid; } else { end = mid; } } if (array[end] == target) { return end; } if (array[start] == target) { return start; } return -1; }
解析:
已排序很重要,而且排序是降序还是升序写法也不一样。
写程序先写异常处理,这里对应的是数组为空的情况。
start 和 end 分别初始化为 0 和 array.size() - 1。
取中值使用 mid = start + (end - start) / 2; 目的是为了防止 start + end 的值超出int范围发生溢出错误。
循环停止条件为 start < end-1;没有等号,如果取等号,那么有可能进入死循环,如:start = 1; end = 2; 那么 mid = 1;那么此时如果令 start = mid,程序将进入死循环。
循环停止时肯定有 start + 1 == end;或者数组元素只有一个,也就是说 start 和 end 要么相邻(数组元素个数大于1),要么相交(数组元素个数为1),那么都可以归结为最后的判断语句,根据题目的要求(第一次出现还是最后一次出现)确定判断顺序。
模板 2:(不推荐)
模板 1 是start == end - 1 时停止循环,下面给出另一种处理,即 start == end时停止循环。
First pos
int binarySearch(vector<int> &array, int target) { if (array.size() == 0) { return -1; } int start = 0; int end = array.size() - 1; int mid; while (start < end) { mid = start + (end - start) / 2; if (array[mid] < target) { start = mid + 1; } else if (array[mid] > target) { end = mid - 1; } else { end = mid; } } if (array[end] == target) { return end; } return -1; }
Last pos
按照模板 1 的逻辑,写成下面这样(这是错误的!!!)
int binarySearchLast(vector<int> &array, int target) { if (array.size() == 0) { return -1; } int start = 0; int end = array.size() - 1; int mid; while (start < end) { mid = start + (end - start) / 2; if (array[mid] < target) { start = mid + 1; } else if (array[mid] > target) { end = mid - 1; } else { start = mid; } } if (array[start] == target) { return start; } return -1; }
看上去逻辑好像很对,但是有一个很严重的错误,那就是有可能会进入死循环:如 start 和 end 指向 1 和 1 且 start = end; 那么此时 mid = start;start = end;相当于start 始终不会变,关键就在于循环条件的判断。那么为什么会造成这个原因呢?仔细想一想就会知道,问题出在求 mid 上,对 2 取模, 2 和 3 的结果是一样的,就是说两个数相邻,那么这两个数的“中值”(mid = start + (end - start)/ 2)始终是第一个,如果程序循环中需要移动候选区间,就有可能造成死循环。就像模板2 中求第一个位置就不会发生死循环,因为移动的是end,除非 start = end,否则 end 是 不会等于mid 的,相反,在求最后一个位置是,若循环条件允许start + 1 == end,那么当需要移动 start 时,就有可能遇到 start 一直等于 mid 的情况, 故不推荐此循环判断方案, 采用模板一的方案,在 start + 1 == end时停止循环,然后根据需要决定 start 和 end 的判断顺序 。当然也可以用模板二的循环方案,只是一定要避免发生死循环的情况。
Last pos (正确的解法)
int binarySearchLast(vector<int> &array, int target) { if (array.size() == 0) { return -1; } int start = 0; int end = array.size() - 1; int mid; while (start < end - 1) { mid = start + (end - start) / 2; if (array[mid] < target) { start = mid + 1; } else if (array[mid] > target) { end = mid - 1; } else { start = mid; } } if (array[end] == target) { return end; } if (array[start] == target) { return start; } return -1; }