面试算法大全-二分查找总结

- 日理万妓 2022-10-06 13:58 140阅读 0赞

## 15、 二分查找 ##

public class BinarySearch {
        
        /**
         *第一种：递归
         */
        public static int recursionBinarySearch(int[]arr,int key,int low,int high){
        
            if(key<arr[low]||key>arr[high]||low>high){
        
                return-1;
            }
            int middle=(low+high)/2;            //初始中间位置
            if(arr[middle]>key){
        
                //比关键字大则关键字在左区域
                return recursionBinarySearch(arr,key,low,middle-1);
            }else if(arr[middle]<key){
        
                //比关键字小则关键字在右区域
                return recursionBinarySearch(arr,key,middle+1,high);
            }else{
        
                return middle;
            }
        }
        /**
         *第二种：非递归
         */
        public static int commonBinarySearch(int[] arr,int key){
        
            int low = 0;
            int high = arr.length - 1;
            int middle = 0;			//定义middle
    
            if(key < arr[low] || key > arr[high] || low > high){
        
                return -1;
            }
    
            while(low <= high){
        
                middle = (low + high) / 2;
                if(arr[middle] > key){
        
                    //比关键字大则关键字在左区域
                    high = middle - 1;
                }else if(arr[middle] < key){
        
                    //比关键字小则关键字在右区域
                    low = middle + 1;
                }else{
        
                    return middle;
                }
            }
            return -1;		//最后仍然没有找到，则返回-1
        }
        public static void main(String[] args) {
        
            int[] arr = {
        1,3,5,7,9,11};
            int key = 4;
            //int position = recursionBinarySearch(arr,key,0,arr.length - 1);
    
            int position = commonBinarySearch(arr, key);
    
            if(position == -1){
        
                System.out.println("查找的是"+key+",序列中没有该数！");
            }else{
        
                System.out.println("查找的是"+key+",找到位置为："+position);
            }
        }
    }

解题模板

int binarySearch(int[] nums, int target) {
        
        int left = 0, right = ...;
    
        while(...) {
        
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
        
                ...
            } else if (nums[mid] < target) {
        
                left = ...
            } else if (nums[mid] > target) {
        
                right = ...
            }
        }
        return ...;
    }

一、寻找一个数（基本的二分搜索）

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

二、寻找左侧边界的二分搜索

int left_bound(int[] nums, int target) {
        
        int left = 0, right = nums.length - 1;
        // 搜索区间为 [left, right]
        while (left <= right) {
        
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
        
                // 搜索区间变为 [mid+1, right]
                left = mid + 1;
            } else if (nums[mid] > target) {
        
                // 搜索区间变为 [left, mid-1]
                right = mid - 1;
            } else if (nums[mid] == target) {
        
                // 收缩右侧边界
                right = mid - 1;
            }
        }
        // 检查出界情况
        if (left >= nums.length || nums[left] != target)
            return -1;
        return left;
    }

三、寻找右侧边界的二分查找

int right_bound(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[mid] == target) {
        
                // 这里改成收缩左侧边界即可
                left = mid + 1;
            }
        }
        // 这里改为检查 right 越界的情况，见下图
        if (right < 0 || nums[right] != target)
            return -1;
        return right;
    }

#### **二分查找leetcode经典例题** ####

#### [二分查找][Link 1] ####

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

#### [猜数字大小][Link 2] ####

/* The guess API is defined in the parent class GuessGame.
       @param num, your guess
       @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
          int guess(int num); */
    
    public class Solution extends GuessGame {
        
        public int guessNumber(int n) {
        
            int low = 1;
            int high = n;
            while (low <= high) {
        
                int mid = low + (high - low) / 2;
                int res = guess(mid);
                if (res == 0)
                    return mid;
                else if (res < 0)
                    high = mid - 1;
                else
                    low = mid + 1;
            }
            return -1;
        }
    }

#### [搜索旋转排序数组][Link 3] ####

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

#### [寻找峰值][Link 4] ####

方法一：递归二分查找

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

方法二：迭代二分查找

public class Solution {
        
        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;
        }
    }

#### [旋转数组的最小数字][Link 5] ####

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

#### [在排序数组中查找元素的第一个和最后一个位置][Link 6] ####

class Solution {
        
        public int[] searchRange(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 new int[]{
        leftIdx, rightIdx};
            } 
            return new int[]{
        -1, -1};
        }
    
        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;
        }
    }

#### [寻找重复数][Link 7] ####

class Solution {
        
        public int findDuplicate(int[] nums) {
        
            int n = nums.length;
            int l = 1, r = n - 1, ans = -1;
            while (l <= r) {
        
                int mid = (l + r) >> 1;
                int cnt = 0;
                for (int i = 0; i < n; ++i) {
        
                    if (nums[i] <= mid) {
        
                        cnt++;
                    }
                }
                if (cnt <= mid) {
        
                    l = mid + 1;
                } else {
        
                    r = mid - 1;
                    ans = mid;
                }
            }
            return ans;
        }
    }

#### [最长上升子序列][Link 8] ####

贪心 + 二分查找

class Solution {
        
        public int lengthOfLIS(int[] nums) {
        
            int len = 1, n = nums.length;
            if (n == 0) {
        
                return 0;
            }
            int[] d = new int[n + 1];
            d[len] = nums[0];
            for (int i = 1; i < n; ++i) {
        
                if (nums[i] > d[len]) {
        
                    d[++len] = nums[i];
                } else {
        
                    int l = 1, r = len, pos = 0; // 如果找不到说明所有的数都比 nums[i] 大，此时要更新 d[1]，所以这里将 pos 设为 0
                    while (l <= r) {
        
                        int mid = (l + r) >> 1;
                        if (d[mid] < nums[i]) {
        
                            pos = mid;
                            l = mid + 1;
                        } else {
        
                            r = mid - 1;
                        }
                    }
                    d[pos + 1] = nums[i];
                }
            }
            return len;
        }
    }

[Link 1]: https://leetcode-cn.com/problems/binary-search/
[Link 2]: https://leetcode-cn.com/problems/guess-number-higher-or-lower/
[Link 3]: https://leetcode-cn.com/problems/search-in-rotated-sorted-array/
[Link 4]: https://leetcode-cn.com/problems/find-peak-element/
[Link 5]: https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/
[Link 6]: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[Link 7]: https://leetcode-cn.com/problems/find-the-duplicate-number/
[Link 8]: https://leetcode-cn.com/problems/longest-increasing-subsequence/