二分查找 ﹏ヽ暗。殇╰゛Y 2024-04-18 23:03 0阅读 0赞 **二分查找**,最基本的算法之一,也是面试中常被考察的重点,因为基本的算法最能反映出一个人的基础是否扎实。本文对二分查找相关题目做一个总结。 (本人第一次面试就被问到了,自面试以来第二个要求手撕的算法,当时没写出来,看到这篇文章,觉得很详细,转载一下) **1. 给定一个有序(非降序)数组A,求任意一个i使得A\[i\]等于target,不存在则返回-1** 这个是最原始的二分查找题目,利用数组的有序特性,拆半查找,使得查找时间复杂度为O(logN)。请参考实现代码与注释。 int search(int A[], int n, int target) { int low = 0, high = n-1; while(low <= high) { // 注意:若使用(low+high)/2求中间位置容易溢出 int mid = low+((high-low)>>1); if(A[mid] == target) return mid; else if(A[mid] < target) low = mid+1; else // A[mid] > target high = mid-1; } return -1; } **2. 给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A\[i\]等于target,不存在则返回-1** 此题也就是求target在数组中第一次出现的位置。这里可能会有人想先直接用原始的二分查找,如果不存在直接返回-1,如果存在,然后再顺序找到这个等于target值区间的最左位置,这样的话,最坏情况下的复杂度就是O(n)了,没有完全发挥出二分查找的优势。这里的解法具体过程请参考实现代码与注释。 int searchFirstPos(int A[], int n, int target) { if(n <= 0) return -1; int low = 0, high = n-1; while(low < high) { int mid = low+((high-low)>>1); if(A[mid] < target) low = mid+1; else // A[mid] >= target high = mid; } /* 循环过程中,当low大于0时,A[low-1]是小于target的,因为A[mid] < target时, low=mid+1;当high小于n-1时,A[high]是大于等于target的,因为A[mid] >= target时, high = mid;循环结束时,low 等于 high,所以,如果A[low](A[high])等于target, 那么low(high)就是target出现的最小位置,否则target在数组中不存在。 */ if(A[low] != target) return -1; else return low; } **3. 给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A\[i\]等于target,不存在则返回-1** 此题也就是求target在数组中最后一次出现的位置。与上一题基本一样,但是有个地方要注意,具体请参考实现代码与注释。 int searchLastPos(int A[], int n, int target) { if(n <= 0) return -1; int low = 0, high = n-1; while(low < high) { /* 这里中间位置的计算就不能用low+((high-low)>>1)了,因为当low+1等于high 且A[low] <= target时,会死循环;所以这里要使用low+((high-low+1)>>1), 这样能够保证循环会正常结束。 */ int mid = low+((high-low+1)>>1); if(A[mid] > target) high = mid-1; else // A[mid] <= target low = mid; } /* 循环过程中,当high小于n-1时,A[high+1]是大于target的,因为A[mid] > target时, high=mid-1;当low大于0时,A[low]是小于等于target的,因为A[mid] <= target时, low = mid;循环结束时,low 等于 high,所以,如果A[high](A[low])等于target, 那么high(low)就是target出现的最大位置,否则target在数组中不存在。 */ if(A[high] != target) return -1; else return high; } **4. 给定一个有序(非降序)数组A,可含有重复元素,求最大的i使得A\[i\]小于target,不存在则返回-1。** 也就是求小于target的最大元素的位置。请参考实现代码与注释。 int searchLastPosLessThan(int A[], int n, int target) { if(n <= 0) return -1; int low = 0, high = n-1; while(low < high) { int mid = low+((high-low+1)>>1); // 注意,不要导致死循环 if(A[mid] < target) low = mid; else // A[mid] >= target high = mid-1; } /* 循环过程中,当low大于0时,A[low]是小于target的,因为A[mid] < target时, low=mid;当high小于n-1时,A[high+1]是大于等于target的,因为A[mid] >= target时, high = mid-1;循环结束时,low 等于 high,所以,如果A[low](A[high])小于target, 那么low(high)就是要找的位置,否则不存在这样的位置(A[0] >= target时)。 */ return A[low] < target ? low : -1; } **5. 给定一个有序(非降序)数组A,可含有重复元素,求最小的i使得A\[i\]大于target,不存在则返回-1。** 也就是求大于target的最小元素的位置。请参考实现代码与注释。 int searchFirstPosGreaterThan(int A[], int n, int target) { if(n <= 0) return -1; int low = 0, high = n-1; while(low < high) { int mid = low+((high-low)>>1); if(A[mid] > target) high = mid; else // A[mid] <= target low = mid+1; } /* 循环过程中,当low大于0时,A[low-1]是小于等于target的,因为A[mid] <= target时, low=mid+1;当high小于n-1时,A[high]是大于target的,因为A[mid] > target时, high = mid;循环结束时,low 等于 high,所以,如果A[high](A[low])大于target, 那么high(low)就是要找的位置,否则不存在这样的位置(A[n-1] <= target时)。 */ return A[high] > target ? high : -1; } **6. 给定一个有序(非降序)数组A,可含有重复元素,求target在数组中出现的次数** 求出第一次出现位置和最后一次出现位置。由于前面都已实现,这里不多解释。请参考实现代码与注释 int count(int A[], int n, int target) { int firstPos = searchFirstPos(A, n, target); // 第一次出现位置 if(firstPos == -1) return 0; int lastPos = searchLastPos(A, n, target); // 最后一次出现位置 return lastPos-firstPos+1; // 出现次数 } 此题描述或者改为求目标值在数组中的索引范围。 **7. 给定一个有序(非降序)数组A,若target在数组中出现,返回位置,若不存在,返回它应该插入的位置** 如 \[1,3,5,6\], 5 → 2 \[1,3,5,6\], 2 → 1 \[1,3,5,6\], 7 → 4 \[1,3,5,6\], 0 → 0 int searchInsert(int A[], int n, int target) { // 如果比最大值还大,那插入位置就是位置n if(A[n-1] < target) return n; int low = 0, high = n-1; while(low < high) { int mid = low+((high-low)>>1); if(A[mid] >= target) high = mid; else // A[mid] < target low = mid+1; } /* 循环过程中,当low大于0时,A[low-1]是小于target的,因为A[mid] < target时, low=mid+1;当high小于n-1时,A[high]是大于等于target的,因为A[mid] >= target时, high = mid;循环结束时,low 等于 high,所以,如果A[low](A[high])等于target, 那么low(high)就是target出现的位置,否则low就是target在数组中应该插入的位置。 */ return high; } **8. 给定一个有序(非降序)数组A,可含有重复元素,求绝对值最小的元素的位置** 找第一个大于等于0的位置,然后和前一个元素的绝对值比较,返回绝对值较小的元素的位置。请参考实现代码与注释 int searchMinAbs(int A[], int n) { int low = 0, high = n-1; while(low < high) { int mid = low+((high-low)>>1); if(A[mid] < 0) low = mid+1; else // A[mid] >= 0 high = mid; } /* 循环结束时,如果low != n-1,A[low] >= 0,如果low>0,A[low-1] < 0 */ if(low > 0 && abs(A[low-1]) < abs(A[low])) return low-1; else return low; } **9. 给定一个有序(非降序)数组A和一个有序(非降序)数组B,可含有重复元素,求两个数组合并结果中的第k(k>=0)个数字。** 这个题目出现了两个数组,有序的,不管怎样我们就应该首先考虑二分查找是否可行。若使用顺序查找,时间复杂度最低为O(k),就是类似归并排序中的归并过程。使用用二分查找时间复杂度为O(logM+logN)。二分查找的具体实现过程请参考实现代码与注释。 int findKthIn2SortedArrays(int A[], int m, int B[], int n, int k) { if(m <= 0) // 数组A中没有元素,直接在B中找第k个元素 return B[k]; if(n <= 0) // 数组B中没有元素,直接在A中找第k个元素 return A[k]; int i = (m-1)>>1; // 数组A的中间位置 int j = (n-1)>>1; // 数组B的中间位置 if(A[i] <= B[j]) // 数组A的中间元素小于等于数组B的中间元素 { /* 设x为数组A和数组B中小于B[j]的元素数目,则i+1+j+1小于等于x, 因为A[i+1]到A[m-1]中还可能存在小于等于B[j]的元素; 如果k小于i+1+j+1,那么要查找的第k个元素肯定小于等于B[j], 因为x大于等于i+1+j+1;既然第k个元素小于等于B[j],那么只 需要在A[0]~A[m-1]和B[0]~B[j]中查找第k个元素即可,递归调用下去。 */ if(k < i+1+j+1) { if(j > 0) return findKthIn2SortedArrays(A, m, B, j+1, k); else // j == 0时特殊处理,防止死循环 { if(k == 0) return min(A[0], B[0]); if(k == m) return max(A[m-1], B[0]); return A[k] < B[0] ? A[k] : max(A[k-1], B[0]); } } /* 设y为数组A和数组B中小于于等于A[i]的元素数目,则i+1+j+1大于等于y; 如果k大于等于i+1+j+1,那么要查找到第k个元素肯定大于A[i],因为 i+1+j+1大于等于y;既然第k个元素大于A[i],那么只需要在A[i+1]~A[m-1] 和B[0]~B[n-1]中查找第k-i-1个元素,递归调用下去。 */ else return findKthIn2SortedArrays(A+i+1, m-i-1, B, n, k-i-1); } // 如果数组A的中间元素大于数组B的中间元素,那么交换数组A和B,重新调用即可 else return findKthIn2SortedArrays(B, n, A, m, k); } **10. 一个有序(升序)数组,没有重复元素,在某一个位置发生了旋转后,求target在变化后的数组中出现的位置,不存在则返回-1** 如 0 1 2 4 5 6 7 可能变成 4 5 6 7 0 1 2 我们先比较中间元素是否是目标值,如果是返回位置。如果不是,我们就应该想办法将搜索区间减少一半。因为存在旋转变化,所以我们要多做一些判断。我们知道因为只有一次旋转变化,所以中间元素两边的子数组肯定有一个是有序的,那么我们可以判断target是不是在这个有序的子数组中,从而决定是搜索这个子数组还是搜索另一个子数组。具体请参考实现代码与注释。 int searchInRotatedArray(int A[], int n, int target) { int low = 0, high = n-1; while(low <= high) { int mid = low+((high-low)>>1); if(A[mid] == target) return mid; if(A[mid] >= A[low]) { // low ~ mid 是升序的 if(target >= A[low] && target < A[mid]) high = mid-1; else low = mid+1; } else { // mid ~ high 是升序的 if(target > A[mid] && target <= A[high]) low = mid+1; else high = mid-1; } } return -1; } 如果这样的数组中存在重复元素,还能使用二分吗?答案是不能。请看几个例子 \[1, 2, 2, 2, 2\], \[2, 1, 2, 2, 2\], \[2, 2, 1, 2, 2\], \[2, 2, 2, 1, 2\], \[2, 2, 2, 2, 1\]这些都是有第一个数组旋转一次变化来的,我们不能通过二分确定是否存在元素1. **11. 一个有序(升序)数组,没有重复元素,在某一个位置发生了旋转后,求最小值所在位置** 如果中间元素小于左端元素,则最小值在左半区间内(包含中间元素);如果中间元素大于右端元素,则最小值在右半区间内(包含中间元素)。请参考实现代码与注释。 int searchMinInRotatedArray(int A[], int n) { if(n == 1) return 0; int low = 0, high = n-1; while(low < high-1) // 保证mid != low且mid != high { int mid = low+((high-low)>>1); if(A[mid] < A[low]) // 最小值在low~mid high = mid; else // A[mid] > A[low], // 最小值在mid和high之间 low = mid; } return A[low] < A[low+1] ? low : low+1; } **12. 一个有序(升序)数组,没有重复元素,在某一个位置发生了旋转后,求第k(k > 0)小元素的位置** 我们可以利用上一题的解答,求出最小值所在位置后,便可以求出第k小元素。请参考实现代码与注释 int searchKthInRotatedArray(int A[], int n, int k) { int posMin = searchMinInRotatedArray(A, n); return (posMin+k-1)%n; }
相关 二分查找 int binary_search(int num, int p, int len) { int high,low,mid; low = 0 川长思鸟来/ 2022年06月14日 09:16/ 0 赞/ 155 阅读
相关 二分查找 网上有看到说大多数程序员都不能写出二分查找的算法,所以呢,我不能成为那大多数程序员中的一个,果然瞎琢磨了半天,还是写出来了,mark下吧。 二分查找的数组得是从小到大升序排序 野性酷女/ 2022年06月04日 09:19/ 0 赞/ 162 阅读
相关 查找——二分查找 基本思想 二分查找是建立在有序顺序表基础上的!步骤如下: 1. 将表中间位置记录的关键字与给定K值进行比较,若两者相等,则查找成功。 2. 蔚落/ 2022年03月27日 03:46/ 0 赞/ 291 阅读
相关 二分查找 Binary Search: Recursive algorithm > ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_ 喜欢ヅ旅行/ 2022年03月17日 02:18/ 0 赞/ 233 阅读
相关 二分查找 二分查找: 适用有序数组 public class BinarySearch { public static int[] arr = {1, 清疚/ 2022年03月09日 06:18/ 0 赞/ 196 阅读
相关 二分查找 1 二分查找 二分查找是一个基础的算法,也是面试中常考的一个知识点。二分查找就是将查找的键和子数组的中间键作比较,如果被查找的键小于中间键,就在左子数组继续查找;如果 本是古典 何须时尚/ 2022年03月08日 10:28/ 0 赞/ 428 阅读
相关 二分查找 说在前面的话 略略略略略略啦略啦略啦略啦略略略啦啦啦啦略啦略略略———当你很认真的把这个读出声的时候,你会发现读完之后你会笑一下,然后笑骂了一下博主真傻bi,最后跟着也骂 谁借莪1个温暖的怀抱¢/ 2022年02月28日 14:24/ 0 赞/ 233 阅读
相关 二分查找 一下是一个正确的二分查找程序: int search(int array[], int n, int v) { int l 素颜马尾好姑娘i/ 2022年02月03日 14:11/ 0 赞/ 210 阅读
相关 二分查找 1.二分查找的定义 二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。 折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 亦凉/ 2021年11月11日 12:44/ 0 赞/ 372 阅读
还没有评论,来说两句吧...