【二分查找专题】剑指 Offer 53 – I. 在排序数组中查找

共以下 9 个回答

• 小肸 永久会员 2023年9月3日 下午4:32

  class Solution {
      public int search(int[] nums, int target) {
          int startIndex = getIndexByBinary(nums, target, true);
          int endIndex = getIndexByBinary(nums, target, false) - 1;
          if (startIndex <= endIndex && endIndex < nums.length 
                  && nums[startIndex] == target && nums[endIndex] == target) {
              return endIndex - startIndex + 1;        
          }
          return 0;
      }
      //lower: true找到nums数组中第一个大于等于target的元素下标
      //lower: false找到nums数组中第一个大于target的元素下标
      int getIndexByBinary(int[] nums, int target, boolean lower) {
          int l = 0, r = nums.length - 1, res = nums.length;
          while (l <= r) {
              int mid = (l + ((r - l) >> 1));
              if (nums[mid] > target || (lower && nums[mid] >= target)) {
                  r = mid - 1;
                  res = mid;
              } else {
                  l = mid + 1;
              }
          }
          return res;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• sc_Yang 普通 2023年9月2日 下午5:37

  两种方法，暴力搜索和寻找第一个小于target的元素的下标

  class Solution {
  public:
      // 暴力搜索
      int search_bl(vector<int>& nums, int target) {
          int count=0;
          for(auto x : nums){
              if(x==target){
                  count++;
              }else if(x > target){
                  return count;
              }
          }
          return count;
      }
      // 二分法
      int search(vector<int>& nums, int target) {
          int count=0;
          int n = nums.size();
          if(n==0) return 0;
          if(nums[n-1]<target) return 0;
          int l=0, r=n-1;
          while(l<r){
              int m = l + (r-l)/2;
              if(nums[m]<target){
                  l = m+1;
              }else if(nums[m]>target){
                  r = m-1;
              }else{
                  while(m>=0 && nums[m]==target) {
                      m--;
                  }
                  l = m+1;
                  break;
              }    
          }
          while(l<n && nums[l]==target){
              l++;
              count++;
          }
          return count;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• Sheng 永久会员 2023年9月2日 下午4:30

  //统计有序数组中某个数字出现的次数
  
  class Solution {
      public int serach(int[] nums, int target) {
          if(nums == null || nums.length == 0) return 0;
  
          int begin = floor_lower(nums, target);
          int end = floor_upper(nums, target);
          if(begin == -1) 
              return 0;//找不到该元素
          return end - begin +1;
      }
  
      //如果数组中存在元素等于target，则返回第一个等于target的下标，
      //如果不存在，则返回-1
      public int floor_lower(int[] arr, int target) {
          //如果都不存在，则返回-1
          if(arr[0] > target) return -1;
          if(arr[0] == target) return 0;
  
          int l = 0;
          int r = arr.length - 1;
          int mid = -1;
          while(l < r) {
              mid = (l + r + 1) / 2;
              if(arr[mid] > target) {
                  r = mid -1;
              }
              else if(arr[mid] < target) {
                  l = mid;
              }
              else {//arr[mid] = target
                  r = mid - 1;
              }
          }
          if(l + 1 < arr.length && arr[l + 1] == target) {
              return l + 1;//l就是第一个小于target 的元素的下标，如果存在等于target的元素，一定是l+1
          }
          return -1;
      }
  
      //如果数组中存在元素等于target，则返回最后一个等于target的元素的下标，
      //如果不存在，则返回-1
      public int floor_upper(int[] arr, int target) {
          //如果都不存在，则返回-1
          if(arr[arr.length-1] < target) return -1;
          if(arr[arr.length-1] == target) return arr.length-1;
  
          int l = 0;
          int r = arr.length - 1;
          int mid = -1;
          while(l < r) {
              mid = (l + r) / 2;
              if(arr[mid] > target) {
                  r = mid;
              }
              else if(arr[mid] < target) {
                  l= mid + 1;
              }
              else {//arr[mid] = target
                  l = mid + 1;
              }
          }
          //l就是第一个大于target 的元素的下标，如果存在等于target的元素，一定是l-1
          if(l - 1 >= 0 && arr[l - 1] == target) {
              return l - 1; 
          }
          return -1;//找不到该元素
      }
  }
  

  1 赞同 2 条回复

  登录以回复
  • 我一定要坚持打卡 普通 @ Sheng 2023年9月3日 上午11:20

    哥们，你这个答案对于 [1,1,1,1,1] target =1 这个用例能够通过吗？

    登录以回复
  • 我一定要坚持打卡 普通 @ Sheng 2023年9月3日 上午11:21

    也就是如果没有存在大于target和小于target的数值存在的话，能通过吗？

    登录以回复
• c 普通 2023年8月31日 下午7:57

  二分

  class Solution {
      public int search(int[] nums, int target) {
          int leftIdx = binarySearch(nums, target, true);
          int rightIdx = binarySearch(nums, target, false) - 1;
          if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
              return rightIdx - leftIdx + 1;
          } 
          return 0;
      }
  
      public int binarySearch(int[] nums, int target, boolean lower) {
          int left = 0, right = nums.length - 1, ans = nums.length;
          while (left <= right) {
              int mid = (left + right) / 2;
              if (nums[mid] > target || (lower && nums[mid] >= target)) {
                  right = mid - 1;
                  ans = mid;
              } else {
                  left = mid + 1;
              }
          }
          return ans;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• sincere 普通 2023年8月31日 下午2:12

  • 思路：有序数组搜索=二分查找，左闭右开，按照之前的变形二分查找，找第一个大于target的和第一个大于target-1的，这里不用ans临时存储了，直接返回left，可以处理右边界的问题
  • 复杂度：时间复杂度O(logn)，空间复杂度O(1)

  class Solution {
      public int search(int[] nums, int target) {
          return helper(nums, target) - helper(nums, target - 1);
      }
  
      // 寻找第一个大于target的元素下标
      public int helper(int[] arr, int target) {
          int left = 0;
          int right = arr.length;
          while (left < right) {
              int mid = (right - left) / 2 + left;
              if (arr[mid] <= target) {
                  left = mid + 1;
              } else {
                  right = mid;
              }
          }
          return left;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• 别扒拉我 普通 2023年8月29日 上午12:03

  二分判断

  lass Solution {
      public int search(int[] nums, int target) {
          int left = 0, right = nums.length-1;
          while(left <= right){
              int mid = left + (right - left)/2;
              if(nums[mid] < target){
                  left = mid + 1;
              }else if(nums[mid] > target){
                  right = mid -1;
              }else{
                  if(nums[left] == nums[right]){
                      return right - left + 1;
                  }
                  if(nums[left] < target){
                      left++;
                  }
                  if(nums[right] > target){
                      right--;
                  }
              }
          }
          return 0;
      }
  }
  

  0 赞同 0 条回复

  登录以回复
• JustRtn 普通 2023年8月28日 下午6:29

  先二分法找到第一个等于给定值的下标，然后得到个数

  class Solution {
  public:
      int search(vector<int>& nums, int target) {
          int low = 0;
          int high = nums.size() - 1;
          int startPos { -1 };
  
          while (low <= high) {
              int mid = low + ((high - low) >> 1);
              if (target < nums[mid]) {
                  high = mid - 1;
              } else if (target > nums[mid]) {
                  low = mid + 1;
              } else {
                  if (mid == 0 || nums[mid-1] != target) {
                      startPos = mid;
                      break;
                  } else {
                      high = mid - 1;
                  }
              }
          }
          int size { 0 };
          if (startPos != -1) {
              while (startPos < nums.size() && nums[startPos] == target) {
                  startPos++;
                  size++;
              }
          }
          return size;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 行动派小彩笔 普通 2023年8月27日 下午9:00

  // 二分的思想，时间复杂度为O(logn)
  class Solution {
  public:
      int binary1(vector<int>&nums,int left,int right,int target)
      {
          while(left+1!=right)
          {
              int mid = (left+right)/2;
              if(nums[mid]<target) left=mid;
              else right = mid;
          }
          return left+1;
      }
      int binary2(vector<int>&nums,int left,int right,int target)
      {
          while(left+1!=right)
          {
              int mid = (left+right)/2;
              if(nums[mid]>target) right=mid;
              else left = mid;
          }
          return right-1;
      }
      int search(vector<int>& nums, int target) {
          if(!nums.size()) return 0;
          int left = binary1(nums,-1,nums.size(),target);
          int right = binary2(nums,-1,nums.size(),target);
          cout<<left<<" "<<right<<endl;
          return right-left+1;
      }
  };
  

  0 赞同 0 条回复

  登录以回复
• 塔底的仰望 永久会员 2023年8月27日 下午7:07

  class Solution {
      public int search(int[] nums, int target) {
          if (nums.length == 0 || nums[nums.length - 1] < target) {
              return 0;
          }
          int l = 0;
          int r = nums.length - 1;
         while (l + 1 < r) {
             int mid = (r -l) / 2 + l;
             if (nums[mid] >= target) {
                  r = mid -1;
             } else {
                  l = mid;
             }
         }
         int count = 0;
         while (l < nums.length) {
             if (nums[l] == target) {
                 count++;
             } else if (nums[l] > target) {
                 break;
             }
             l++;
         }
         return count;
      }
  }
  

  1 赞同 0 条回复

  登录以回复