算法及数据结构系列 - 二分查找

打印 上一主题 下一主题

主题 1014|帖子 1014|积分 3042

系列文章目次
算法及数据结构系列 - BFS算法


  
二分查找

框架思绪

  1. int binarySearch(int[] nums, int target) {
  2.     int left = 0, right = ...;
  3.     while(...) {
  4.         int mid = left + (right - left) / 2;
  5.         if (nums[mid] == target) {
  6.             ...
  7.         } else if (nums[mid] < target) {
  8.             left = ...
  9.         } else if (nums[mid] > target) {
  10.             right = ...
  11.         }
  12.     }
  13.     return ...;
  14. }
复制代码
计算 mid 时需要防止溢出,代码中 left + (right - left) / 2 就和 (left + right) / 2 的效果雷同,但是有效防止了 left 和 right 太大直接相加导致溢出。
经典题型

二分查找

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int left = 0, right = nums.length - 1;
  4.         while(left <= right){
  5.             int mid = left + (right - left)/2;
  6.             if(nums[mid] == target){
  7.                 return mid;
  8.             }else if (nums[mid] > target){
  9.                 right = mid - 1;
  10.             }else{
  11.                 left = mid + 1;
  12.             }
  13.         }
  14.         return -1;
  15.     }
  16. }
复制代码
寻找左侧界限

留意: 当 val 不存在时,得到的索引恰恰是比 val 大的最小元素索引
  1. int left_bound(int[] nums, int target) {
  2.     if (nums.length == 0) return -1;
  3.     int left = 0;
  4.     int right = nums.length; // 注意
  5.    
  6.     while (left < right) { // 注意
  7.         int mid = (left + right) / 2;
  8.         if (nums[mid] == target) {
  9.             right = mid;
  10.         } else if (nums[mid] < target) {
  11.             left = mid + 1;
  12.         } else if (nums[mid] > target) {
  13.             right = mid; // 注意
  14.         }
  15.     }
  16.     return left;
  17. }
复制代码
寻找右侧界限

  1. int right_bound(int[] nums, int target) {
  2.     if (nums.length == 0) return -1;
  3.     int left = 0, right = nums.length;
  4.    
  5.     while (left < right) {
  6.         int mid = (left + right) / 2;
  7.         if (nums[mid] == target) {
  8.             left = mid + 1; // 注意
  9.         } else if (nums[mid] < target) {
  10.             left = mid + 1;
  11.         } else if (nums[mid] > target) {
  12.             right = mid;
  13.         }
  14.     }
  15.     return left - 1; // 注意
  16. }
复制代码
刷题

875. 爱吃香蕉的珂珂

珂珂喜欢吃香蕉。这里有 N 堆香蕉,第 i 堆中有 piles 根香蕉。警卫已经离开了,将在 H 小时后回来。
珂珂可以决定她吃香蕉的速度 K (单位:根/小时)。每个小时,她将会选择一堆香蕉,从中吃掉 K 根。如果这堆香蕉少于 K 根,她将吃掉这堆的所有香蕉,然后这一小时内不会再吃更多的香蕉。
珂珂喜欢逐步吃,但仍旧想在警卫回来前吃掉所有的香蕉。
返回她可以在 H 小时内吃掉所有香蕉的最小速度 K(K 为整数)。
提示: 吃每一堆分别要几小时;寻找左侧界限
  1. class Solution {
  2.     public int minEatingSpeed(int[] piles, int H) {
  3.         Arrays.sort(piles);
  4.         int left = 1, right = piles[piles.length - 1] + 1;
  5.         while(left < right){
  6.             int mid = left + (right - left)/2;
  7.             if(canFinish(mid, piles, H)){
  8.                 right = mid;
  9.             }else{
  10.                 left = mid + 1;
  11.             }
  12.         }
  13.         return left;
  14.     }
  15.     public boolean canFinish(int k, int[] piles, int H){
  16.         long tmpHour = 0;
  17.         for(int i = 0; i< piles.length;i++){
  18.             tmpHour += (long)(piles[i] / k);
  19.             if(piles[i] % k > 0){
  20.                 tmpHour ++;
  21.             }
  22.         }
  23.         if(tmpHour <= H){
  24.             return true;
  25.         }else{
  26.             return false;
  27.         }
  28.     }
  29. }
复制代码
1011. 在 D 天内送达包裹的本领

传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
传送带上的第 i 个包裹的重量为 weights。每一天,我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会凌驾船的最大运载重量。
返回能在 D 天内将传送带上的所有包裹送达的船的最低运载本领。
示例:
  1. 输入:weights = [1,2,3,4,5,6,7,8,9,10], D = 5
  2. 输出:15
  3. 解释:
  4. 船舶最低载重 15 就能够在 5 天内送达所有包裹,如下所示:
  5. 第 1 天:1, 2, 3, 4, 5
  6. 第 2 天:6, 7
  7. 第 3 天:8
  8. 第 4 天:9
  9. 第 5 天:10
  10. 请注意,货物必须按照给定的顺序装运,因此使用载重能力为 14 的船舶并将包装分成 (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) 是不允许的。 s
复制代码
  1. class Solution {
  2.     public int shipWithinDays(int[] weights, int D) {
  3.         if(weights.length == 0){
  4.             return 0;
  5.         }
  6.         int len = weights.length;
  7.         int left = weights[0], right = (weights[0] + weights[len -1]) * len / 2 + 1;
  8.         while(left < right){
  9.             int mid = left + (right - left)/2;
  10.             if(canFinish(weights, D, mid)){
  11.                 right = mid;
  12.             }else{
  13.                 left = mid + 1;
  14.             }
  15.         }
  16.         return left;
  17.     }
  18.     public boolean canFinish(int[] w, int D, int cap){
  19.         int i = 0;
  20.         for (int day = 0; day < D; day++) {
  21.             int maxCap = cap;
  22.             while ((maxCap -= w[i]) >= 0) {
  23.                 i++;
  24.                 if (i == w.length)
  25.                     return true;
  26.             }
  27.         }
  28.         return false;
  29.     }
  30. }
复制代码
392. 判定子序列

给定字符串 s 和 t ,判定 s 是否为 t 的子序列。
你可以认为 s 和 t 中仅包含英文小写字母。字符串 t 可能会很长(长度 ~= 500,000),而 s 是个短字符串(长度 <=100)。
字符串的一个子序列是原始字符串删除一些(也可以不删除)字符而不改变剩余字符相对位置形成的新字符串。(例如,"ace"是"abcde"的一个子序列,而"aec"不是)。
  1. class Solution {
  2.     public boolean isSubsequence(String s, String t) {
  3.         int fromIndex = 0;
  4.         for(int i = 0; i < s.length(); i++){
  5.             char tmp = s.charAt(i);
  6.             int j = fromIndex;
  7.             for(; j < t.length(); j++){
  8.                 if(t.charAt(j) == tmp){
  9.                     fromIndex = j + 1;
  10.                     break;
  11.                 }
  12.             }
  13.             if(j == t.length()){
  14.                 return false;
  15.             }
  16.         }
  17.         return true;
  18.     }
  19. }
复制代码
后续挑衅 :
如果有大量输入的 S,称作S1, S2, … , Sk 其中 k >= 10亿,你需要依次检查它们是否为 T 的子序列。在这种情况下,你会怎样改变代码?
  1. class Solution {
  2.     public boolean isSubsequence(String s, String t) {
  3.         int m = s.length(), n = t.length();
  4.         ArrayList<Integer>[] index = new ArrayList[256];
  5.         // 先记下 t 中每个字符出现的位置
  6.         for (int i = 0; i < n; i++) {
  7.             char c = t.charAt(i);
  8.             if (index[c] == null)
  9.                 index[c] = new ArrayList<>();
  10.             index[c].add(i);
  11.         }
  12.         int j = 0; // t 上的指针
  13.         // 借助 index 查找 s[i]
  14.         for (int i = 0; i < m; i++) {
  15.             char c = s.charAt(i);
  16.             // 整个 t 压根儿没有字符 c
  17.             if (index[c] == null) return false;
  18.             int pos = find(index[c], j);
  19.             // 二分搜索区间中没有找到字符 c
  20.             if (pos == index[c].size()) return false;
  21.             // 向前移动指针 j
  22.             j = index[c].get(pos) + 1;
  23.         }
  24.         return true;
  25.     }
  26.     public int find(ArrayList<Integer> arr, int target){
  27.         int left = 0, right = arr.size();
  28.         while(left < right){
  29.             int mid = left + (right - left)/2;
  30.             if(arr.get(mid) == target){
  31.                 right = mid;
  32.             }else if (arr.get(mid) > target){
  33.                 right = mid;
  34.             }else {
  35.                 left = mid + 1;
  36.             }
  37.         }
  38.         return left;
  39.     }
  40. }
复制代码
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。
回复

举报

0 个回复

倒序浏览

快速回复

您需要登录后才可以回帖 登录 or 立即注册

本版积分规则

麻花痒

论坛元老
这个人很懒什么都没写!
快速回复 返回顶部 返回列表