刷题记录

转专业的渣渣写了2周的hci作业。上上周开始刷利口，听了几个刷题辅导班。这周正式开始，用Julie and Julia里的方式，发表一个公开日志，倒计时一年。语言: c++

最近是被class困扰

二分查找
两边闭合 边界查找 查看left right 最终越界情况，因为终止条件是left == right + 1

1. int binary_search(int[] nums, int target) {
   
2.     int left = 0, right = nums.length - 1;
   
3.     while(left <= right) {
   
4.         int mid = left + (right - left) / 2;
   
5.         if (nums[mid] < target) {
   
6.             left = mid + 1;
   
7.         } else if (nums[mid] > target) {
   
8.             right = mid - 1;
   
9.         } else if(nums[mid] == target) {
   
10.             // 直接返回
    
11.             return mid;
    
12.         }
    
13.     }
    
14.     // 直接返回
    
15.     return -1;
    
16. }
    
17. 
    
18. int left_bound(int[] nums, int target) {
    
19.     int left = 0, right = nums.length - 1;
    
20.     while (left <= right) {
    
21.         int mid = left + (right - left) / 2;
    
22.         if (nums[mid] < target) {
    
23.             left = mid + 1;
    
24.         } else if (nums[mid] > target) {
    
25.             right = mid - 1;
    
26.         } else if (nums[mid] == target) {
    
27.             // 别返回，锁定左侧边界
    
28.             right = mid - 1;
    
29.         }
    
30.     }
    
31.     // 最后要检查 left 越界的情况
    
32.     if (left >= nums.length || nums[left] != target) {
    
33.         return -1;
    
34.     }
    
35.     return left;
    
36. }
    
37. 
    
38. int right_bound(int[] nums, int target) {
    
39.     int left = 0, right = nums.length - 1;
    
40.     while (left <= right) {
    
41.         int mid = left + (right - left) / 2;
    
42.         if (nums[mid] < target) {
    
43.             left = mid + 1;
    
44.         } else if (nums[mid] > target) {
    
45.             right = mid - 1;
    
46.         } else if (nums[mid] == target) {
    
47.             // 别返回，锁定右侧边界
    
48.             left = mid + 1;
    
49.         }
    
50.     }
    
51.     // 最后要检查 right 越界的情况
    
52.     if (right < 0 || nums[right] != target) {
    
53.         return -1;
    
54.     }
    
55.     return right;
    
56. }
    

复制代码