devbox
小惠珠哦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】数组复习-二分查找法

作者：小惠珠哦 | 2024-08-09 09:38:40

赞

踩

【数据结构】数组复习-二分查找法

写这篇博客的起因：

刚开始刷力扣，发现没有一个很好的做题方法，在网络上发现了这个博主的评论，如下。感觉挺适合我，所以开始复习一下数据结构。

c++基础主要是看：

刷题主要是看：

  • 3.leetcode-labuladong系列

《labuladong 的算法笔记》纸质书 | labuladong 的算法笔记

一、数组-二分法

问题1：左闭右闭，左闭右开，左开右闭

一般使用左闭右闭和左闭右开比较多

1：左闭右开（left<right）

  1. left=0
  2. right=len(num)-1
  3. m1 = (right - left) // 2 + left
  4. while(left<right):
  5.     m1>t,right=m1
  6.     m1<t,left=m1+1
  7.     m1=t,m1

2：左闭右闭（left<=right）

  1. left=0
  2. right=len(num)-1
  3. m1 = (right - left) // 2 + left
  4. while(left<=right):
  5.     m1>t,right=m1-1
  6.     m1<t,left=m1+1
  7.     m1=t,m1

二、力扣相关例题

704题：二分查找

python语言-左闭右开

  1. from typing import List
  2.  
  3. class Solution:
  4.     def search(self, nums: List[int], target: int) -> int:
  5.  
  6.     # self: 这是一个特殊的参数，用来引用类的实例本身。在类方法中，self 是必须的，但在调用方法时通常不需要显式传入，Python会自动处理。
  7.     # nums: List[int]: 这是函数的第一个参数，命名为 nums，类型注解指示它应该是一个整数列表。
  8.     # target: int: 这是函数的第二个参数，命名为 target，类型注解指示它应该是一个整数。
  9.     # -> int: 这部分指定了函数的返回类型，即该函数会返回一个整数。
  10.  
  11.         left, right = 0, len(nums)
  12.  
  13.         while left < right:
  14.             middle = left + (right - left) // 2
  15.  
  16.             if nums[middle] > target:
  17.                 right = middle
  18.             elif nums[middle] < target:
  19.                 left = middle + 1
  20.             else:
  21.                 return middle
  22.  
  23.         return -1
  24.  
  25. def main():
  26.     # Example usage:
  27.     nums = [-1, 0, 3, 5, 9, 12]
  28.     target = 9
  29.     solution = Solution()
  30.     result = solution.search(nums, target)
  31.     print(f"Index of {target} in {nums}: {result}")
  32.  
  33. if __name__ == "__main__":
  34.     main()

python语言-左闭右闭

  1. from typing import List
  2.  
  3. class Solution:
  4.     def search(self, nums: List[int], target: int) -> int:
  5.  
  6.     # self: 这是一个特殊的参数，用来引用类的实例本身。在类方法中，self 是必须的，但在调用方法时通常不需要显式传入，Python会自动处理。
  7.     # nums: List[int]: 这是函数的第一个参数，命名为 nums，类型注解指示它应该是一个整数列表。
  8.     # target: int: 这是函数的第二个参数，命名为 target，类型注解指示它应该是一个整数。
  9.     # -> int: 这部分指定了函数的返回类型，即该函数会返回一个整数。
  10.  
  11.         left, right = 0, len(nums) - 1  # 定义target在左闭右闭的区间里，[left, right]
  12.  
  13.         while left <= right:
  14.             middle = left + (right - left) // 2
  15.             
  16.             if nums[middle] > target:
  17.                 right = middle - 1  # target在左区间，所以[left, middle - 1]
  18.             elif nums[middle] < target:
  19.                 left = middle + 1  # target在右区间，所以[middle + 1, right]
  20.             else:
  21.                 return middle  # 数组中找到目标值，直接返回下标
  22.         return -1  # 未找到目标值
  23.  
  24. def main():
  25.     # Example usage:
  26.     nums = [-1, 0, 3, 5, 9, 12]
  27.     target = 9
  28.     solution = Solution()
  29.     result = solution.search(nums, target)
  30.     print(f"Index of {target} in {nums}: {result}")
  31.  
  32. if __name__ == "__main__":
  33.     main()

c++语言-左闭右开

  1. # include <vector>
  2.  
  3. class Solution {
  4. public:
  5.     int search(std::vector<int>& nums, int target) {
  6.         int left = 0;
  7.         int right = nums.size(); // right is the index just beyond the end of the vector
  8.  
  9.         while (left < right) {
  10.             int middle = left + (right - left) / 2;
  11.  
  12.             if (nums[middle] > target) {
  13.                 right = middle; // target in left half, [left, middle)
  14.             } else if (nums[middle] < target) {
  15.                 left = middle + 1; // target in right half, [middle + 1, right)
  16.             } else {
  17.                 return middle; // target found at index middle
  18.             }
  19.         }
  20.  
  21.         return -1; // target not found
  22.     }
  23. };
  24.  
  25. // Example usage
  26. #include <iostream>
  27.  
  28. int main() {
  29.     Solution solution;
  30.     std::vector<int> nums = {-1, 0, 3, 5, 9, 12};
  31.     int target = 9;
  32.     int result = solution.search(nums, target);
  33.     std::cout << "Index of " << target << " in nums: " << result << std::endl;
  34.     return 0;
  35. }
  36.

c++语言-左闭右闭

  1. # include <vector>
  2.  
  3. class Solution {
  4. public:
  5.     int search(std::vector<int>& nums, int target) {
  6.         int left = 0;
  7.         int right = nums.size(); // right is the index just beyond the end of the vector
  8.  
  9.         while (left <= right) {
  10.             int middle = left + (right - left) / 2;
  11.  
  12.             if (nums[middle] > target) {
  13.                 right = middle-1; // target in left half, [left, middle)
  14.             } else if (nums[middle] < target) {
  15.                 left = middle + 1; // target in right half, [middle + 1, right)
  16.             } else {
  17.                 return middle; // target found at index middle
  18.             }
  19.         }
  20.  
  21.         return -1; // target not found
  22.     }
  23. };
  24.  
  25. // Example usage
  26. #include <iostream>
  27.  
  28. int main() {
  29.     Solution solution;
  30.     std::vector<int> nums = {-1, 0, 3, 5, 9, 12};
  31.     int target = 9;
  32.     int result = solution.search(nums, target);
  33.     std::cout << "Index of " << target << " in nums: " << result << std::endl;
  34.     return 0;
  35. }
  36.

相关题目：

35题：搜索插入位置

  1.  
  2. #
  3. # @lc app=leetcode.cn id=35 lang=python
  4. #
  5. # [35] 搜索插入位置
  6. #
  7.  
  8. # @lc code=start
  9. from typing import List
  10. class Solution():
  11.     def searchInsert(self, nums: List[int], target: int) -> int:
  12.         """
  13.         :type nums: List[int]
  14.         :type target: int
  15.         :rtype: int
  16.         """
  17.         left = 0
  18.  
  19.         right = len(nums)  # 左闭右开区间 [left, right)
  20.  
  21.         while left < right:  # 区间不为空
  22.  
  23.             # 循环不变量：
  24.  
  25.             # nums[left-1] < target
  26.  
  27.             # nums[right] >= target
  28.  
  29.             mid = left + (right - left) // 2
  30.  
  31.             if nums[mid] < target:
  32.  
  33.                 left = mid + 1  # 范围缩小到 [mid+1, right)
  34.  
  35.             else:
  36.  
  37.                 right = mid  # 范围缩小到 [left, mid)
  38.  
  39.         return left  # 或者 right
  40.  
  41.  
  42. def main():
  43.     nums = [-1, 0, 3, 5, 9, 12]
  44.     target = 8
  45.     solution = Solution()
  46.     result = solution.searchInsert(nums, target)
  47.     print(f"Index of {target} in {nums}: {result}")       
  48.  
  49. if __name__ == "__main__":
  50.     main()
  51.  
  52.  
  53. # @lc code=end
  54.


34题：在排序数组中查找元素的第一个和最后一个位置

  1. #
  2. # @lc app=leetcode.cn id=34 lang=python
  3. #
  4. # [34] 在排序数组中查找元素的第一个和最后一个位置
  5. #
  6.  
  7. # @lc code=start
  8. from typing import List
  9.  
  10. class Solution:
  11.     def searchRange(self, nums: List[int], target: int) -> List[int]:
  12.         left = 0
  13.         right = len(nums) - 1
  14.         result = [-1, -1]
  15.  
  16.         # Edge case: empty list
  17.         if not nums:
  18.             return result
  19.  
  20.         # Binary search for the left boundary of target
  21.         while left <= right:
  22.             middle = left + (right - left) // 2
  23.             if nums[middle] < target:
  24.                 left = middle + 1
  25.             else:
  26.                 right = middle - 1
  27.         # After the loop, `left` is the index of the first occurrence of `target`
  28.         if left < len(nums) and nums[left] == target:
  29.             result[0] = left
  30.         else:
  31.             return result
  32.  
  33.         # Binary search for the right boundary of target
  34.         left = 0
  35.         right = len(nums) - 1
  36.         while left <= right:
  37.             middle = left + (right - left) // 2
  38.             if nums[middle] <= target:
  39.                 left = middle + 1
  40.             else:
  41.                 right = middle - 1
  42.         # After the loop, `right` is the index of the last occurrence of `target`
  43.         result[1] = right
  44.  
  45.         return result
  46.  
  47. def main():
  48.     nums = [-1, 0, 3, 5, 9, 9, 12]
  49.     target = 10
  50.     solution = Solution()
  51.     result = solution.searchRange(nums, target)
  52.     print(f"Indices of {target} in {nums}: {result}")
  53.  
  54. if __name__ == "__main__":
  55.     main()
  1. c++
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. class Solution {
  7. public:
  8.     vector<int> searchRange(vector<int>& nums, int target) {
  9.         vector<int> result = {-1, -1};
  10.         int left = 0;
  11.         int right = nums.size() - 1;
  12.  
  13.         // First binary search to find the leftmost index of target
  14.         while (left <= right) {
  15.             int mid = left + (right - left) / 2;
  16.             if (nums[mid] < target) {
  17.                 left = mid + 1;
  18.             } else if (nums[mid] > target) {
  19.                 right = mid - 1;
  20.             } else {
  21.                 // Found target, adjust right to search left part
  22.                 result[0] = mid;
  23.                 right = mid - 1;
  24.             }
  25.         }
  26.  
  27.         // Second binary search to find the rightmost index of target
  28.         left = 0;
  29.         right = nums.size() - 1;
  30.         while (left <= right) {
  31.             int mid = left + (right - left) / 2;
  32.             if (nums[mid] < target) {
  33.                 left = mid + 1;
  34.             } else if (nums[mid] > target) {
  35.                 right = mid - 1;
  36.             } else {
  37.                 // Found target, adjust left to search right part
  38.                 result[1] = mid;
  39.                 left = mid + 1;
  40.             }
  41.         }
  42.  
  43.         return result;
  44.     }
  45. };
  46.  
  47. int main() {
  48.     vector<int> nums = {-1, 0, 3, 5, 9, 9, 9, 12};
  49.     int target = 9;
  50.     Solution solution;
  51.     vector<int> result = solution.searchRange(nums, target);
  52.     cout << "Indices of " << target << " in nums: [" << result[0] << ", " << result[1] << "]" << endl;
  53.     return 0;
  54. }

367题：有效的完全平方数

  1. #include <iostream>
  2. using namespace std;
  3.  
  4. bool isPerfectSquare(int num) {
  5.     if (num == 0 || num == 1) {
  6.         return true;
  7.     }
  8.     long left = 1;
  9.     long right = num;
  10.     long mid = 0;
  11.     while (left <= right) {
  12.         mid = (left + right + 1) / 2; // 保证处理到右边界
  13.         long long res = mid * mid; // 使用 long long 来存放结果，避免整数溢出
  14.         if (res == num) {
  15.             return true;
  16.         } else if (res > num) {
  17.             // [left, mid-1] 区间继续找
  18.             right = mid - 1;
  19.         } else {
  20.             // [mid+1, right] 区间继续找
  21.             left = mid + 1;
  22.         }
  23.     }
  24.     return false;
  25. }
  26.  
  27. int main() {
  28.     // 测试数据
  29.     int nums[] = {16, 14, 25, 0, 1, 100, 99};
  30.     int n = sizeof(nums) / sizeof(nums[0]);
  31.  
  32.     for (int i = 0; i < n; ++i) {
  33.         cout << "Number " << nums[i] << (isPerfectSquare(nums[i]) ? " is" : " is not") << " a perfect square." << endl;
  34.     }
  35.  
  36.     return 0;
  37. }
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. bool isPerfectSquare(int num) {
  5.     if (num == 0 || num == 1) {
  6.         return true;
  7.     }
  8.     long left = 1;
  9.     long right = num;
  10.     long mid = 0;
  11.     while (left <= right) {
  12.         mid = (left + right + 1) / 2; // 保证处理到右边界
  13.         long long res = mid * mid; // 使用 long long 来存放结果，避免整数溢出
  14.         if (res == num) {
  15.             return true;
  16.         } else if (res > num) {
  17.             // [left, mid-1] 区间继续找
  18.             right = mid - 1;
  19.         } else {
  20.             // [mid+1, right] 区间继续找
  21.             left = mid + 1;
  22.         }
  23.     }
  24.     return false;
  25. }
  26.  
  27. int main() {
  28.     // 测试数据
  29.     int nums[] = {16, 14, 25, 0, 1, 100, 99};
  30.     int n = sizeof(nums) / sizeof(nums[0]);
  31.  
  32.     for (int i = 0; i < n; ++i) {
  33.         cout << "Number " << nums[i] << (isPerfectSquare(nums[i]) ? " is" : " is not") << " a perfect square." << endl;
  34.     }
  35.  
  36.     return 0;
  37. }

本文内容由网友自发贡献，转载请注明出处：https://www.wpsshop.cn/w/小惠珠哦/article/detail/952595
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号