算法 - 二分查找

向右看齐 2022-11-13 09:27 237阅读 0赞

# 基础二分 #

/** * 要求数组有序 ,二分法 * @param arr * @param * @return */
        private static int binarySearch(int[] arr, int left, int right, int findVal) { 
            //给一个出口
            if (left >= right) { 
                return -1;
            }
    
            int mid = (left + right) / 2;
            int midV = arr[mid];
    
            if (midV < findVal) { 
                return binarySearch(arr, mid + 1, right, findVal);
            } else if (midV > findVal) { 
                return binarySearch(arr, left, mid - 1, findVal);
            } else { 
                return mid;
            }
    
        }

这里有一个讲究的地方：

> 如果用mid=(left+right)/2，在运行二分查找程序时可能溢出超时。  
> 因为如果left和right相加超过int表示的最大范围时就会溢出变为负数。  
> 所以如果想避免溢出，不能使用mid=(left+right)/2，应该使用mid=left+(right-left)/2。

还有的方式：

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

同时要注意 left<= right 的退出条件，不然存在以下直接退出-1情况：

search(new int[]{ 1, 2, 3, 4, 5,6}, 4)

# 寻找旋转排序数组中的最小值 #

> 假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 \[0,1,2,4,5,6,7\] 可能变为 \[4,5,6,7,0,1,2\] 。  
> 请找出其中最小的元素。

本题的关键为找间隙，找到那个进行的旋转的间隙位置，其左右就是最小值。

不断逼近间隙，

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

存在一种找到即退出的优化方案：

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

## 存在重复数据 ##

[解析来自leetcode][leetcode]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]  
第一种情况是nums\[pivot\] < nums\[high\]。如下图所示，这说明nums\[pivot\] 是最小值右侧的元素，因此我们可以忽略二分查找区间的右半部分。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]  
第二种情况是 nums\[pivot\]>nums\[high\]。如下图所示，这说明 nums\[pivot\] 是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]

第三种情况是nums\[pivot\]==nums\[high\]。如下图所示，由于重复元素的存在，我们并不能确定 nums\[pivot\] 究竟在最小值的左侧还是右侧，因此我们不能莽撞地忽略某一部分的元素。我们唯一可以知道的是，由于它们的值相同，所以无论 nums\[high\] 是不是最小值，都有一个它的「替代品」nums\[pivot\]，因此我们可以忽略二分查找区间的右端点。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 3]

public int findMin(int[] nums) { 
            int low = 0;
            int high = nums.length - 1;
            while (low < high) { 
                int pivot = low + (high - low) / 2;
                if (nums[pivot] < nums[high]) { 
                    high = pivot;
                } else if (nums[pivot] > nums[high]) { 
                    low = pivot + 1;
                } else { 
                    high -= 1;
                }
            }
            return nums[low];
        }

# 寻找峰值 #

> 峰值元素是指其值大于左右相邻值的元素。  
> 给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。  
> 你可以假设 nums\[-1\] = nums\[n\] = -∞ 。

nums\[-1\] = nums\[n\] = -∞ 这个条件是关键，而且只需要找到一个。

public int findPeakElement(int[] nums) { 
            int l = 0, r = nums.length - 1;
            while (l < r) { 
                int mid = (l + r) / 2;
                if (nums[mid] > nums[mid + 1])
                    r = mid;
                else
                    l = mid + 1;
            }
            return l;
        }

[leetcode]: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/solution/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-de-zui--16/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70]: /images/20221022/3d5834b6be09452eb4a27f2f60c0538b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 1]: /images/20221022/ec5b28cf799d424fba86009cc62ccdde.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 2]: /images/20221022/7db06872857245769a20db4125aadd4c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpdHRsZXdoaXRldmc_size_16_color_FFFFFF_t_70 3]: /images/20221022/ba18ef5db38a41c084e40b30718c33f2.png