34. 在排序數(shù)組中查找元素的第一個和最后一個位置

難度中等985收藏分享切換為英文接收動態(tài)反饋

給定一個按照升序排列的整數(shù)數(shù)組 nums，和一個目標(biāo)值 target。找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

進(jìn)階：

• 你可以設(shè)計并實現(xiàn)時間復(fù)雜度為 O(log n) 的算法解決此問題嗎？

示例 1：

輸入：nums = [5,7,7,8,8,10], target = 8
輸出：[3,4]

示例 2：

輸入：nums = [5,7,7,8,8,10], target = 6
輸出：[-1,-1]

示例 3：

輸入：nums = [], target = 0
輸出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一個非遞減數(shù)組
• -109 <= target <= 109

34. Find First and Last Position of Element in Sorted Array

Medium

5577208Add to ListShare

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

If target is not found in the array, return [-1, -1].

Follow up: Could you write an algorithm with O(log n) runtime complexity?

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Example 3:

Input: nums = [], target = 0
Output: [-1,-1]

Constraints:

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums is a non-decreasing array.
• -109 <= target <= 109

該部分摘自 極客時間-數(shù)據(jù)結(jié)構(gòu)與算法之美

image

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == 0) || (a[mid - 1] != value)) return mid;
      else high = mid - 1;
    }
  }
  return -1;
}

我來稍微解釋一下這段代碼。a[mid]跟要查找的value的大小關(guān)系有三種情況：大于、小于、等于。對于a[mid]>value的情況，我們需要更新high= mid-1；對于a[mid]<value的情況，我們需要更新low=mid+1。這兩點都很好理解。那當(dāng)a[mid]=value的時候應(yīng)該如何處理呢？

如果我們查找的是任意一個值等于給定值的元素，當(dāng)a[mid]等于要查找的值時，a[mid]就是我們要找的元素。但是，如果我們求解的是第一個值等于給定值的元素，當(dāng)a[mid]等于要查找的值時，我們就需要確認(rèn)一下這個a[mid]是不是第一個值等于給定值的元素。

我們重點看第11行代碼。如果mid等于0，那這個元素已經(jīng)是數(shù)組的第一個元素，那它肯定是我們要找的；如果mid不等于0，但a[mid]的前一個元素a[mid-1]不等于value，那也說明a[mid]就是我們要找的第一個值等于給定值的元素。

如果經(jīng)過檢查之后發(fā)現(xiàn)a[mid]前面的一個元素a[mid-1]也等于value，那說明此時的a[mid]肯定不是我們要查找的第一個值等于給定值的元素。那我們就更新high=mid-1，因為要找的元素肯定出現(xiàn)在[low, mid-1]之間。

對比上面的兩段代碼，是不是下面那種更好理解？實際上，很多人都覺得變形的二分查找很難寫，主要原因是太追求第一種那樣完美、簡潔的寫法。而對于我們做工程開發(fā)的人來說，代碼易讀懂、沒Bug，其實更重要，所以我覺得第二種寫法更好。

變體二：查找最后一個值等于給定值的元素

前面的問題是查找第一個值等于給定值的元素，我現(xiàn)在把問題稍微改一下，查找最后一個值等于給定值的元素，又該如何做呢？

如果你掌握了前面的寫法，那這個問題你應(yīng)該很輕松就能解決。你可以先試著實現(xiàn)一下，然后跟我寫的對比一下。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else if (a[mid] < value) {
      low = mid + 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] != value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

我們還是重點看第11行代碼。如果a[mid]這個元素已經(jīng)是數(shù)組中的最后一個元素了，那它肯定是我們要找的；如果a[mid]的后一個元素a[mid+1]不等于value，那也說明a[mid]就是我們要找的最后一個值等于給定值的元素。

如果我們經(jīng)過檢查之后，發(fā)現(xiàn)a[mid]后面的一個元素a[mid+1]也等于value，那說明當(dāng)前的這個a[mid]并不是最后一個值等于給定值的元素。我們就更新low=mid+1，因為要找的元素肯定出現(xiàn)在[mid+1, high]之間。

變體三：查找第一個大于等于給定值的元素

現(xiàn)在我們再來看另外一類變形問題。在有序數(shù)組中，查找第一個大于等于給定值的元素。比如，數(shù)組中存儲的這樣一個序列：3，4，6，7，10。如果查找第一個大于等于5的元素，那就是6。

實際上，實現(xiàn)的思路跟前面的那兩種變形問題的實現(xiàn)思路類似，代碼寫起來甚至更簡潔。

public int bsearch(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] >= value) {
      if ((mid == 0) || (a[mid - 1] < value)) return mid;
      else high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  return -1;
}

如果a[mid]小于要查找的值value，那要查找的值肯定在[mid+1, high]之間，所以，我們更新low=mid+1。

對于a[mid]大于等于給定值value的情況，我們要先看下這個a[mid]是不是我們要找的第一個值大于等于給定值的元素。如果a[mid]前面已經(jīng)沒有元素，或者前面一個元素小于要查找的值value，那a[mid]就是我們要找的元素。這段邏輯對應(yīng)的代碼是第7行。

如果a[mid-1]也大于等于要查找的值value，那說明要查找的元素在[low, mid-1]之間，所以，我們將high更新為mid-1。

變體四：查找最后一個小于等于給定值的元素

現(xiàn)在，我們來看最后一種二分查找的變形問題，查找最后一個小于等于給定值的元素。比如，數(shù)組中存儲了這樣一組數(shù)據(jù)：3，5，6，8，9，10。最后一個小于等于7的元素就是6。是不是有點類似上面那一種？實際上，實現(xiàn)思路也是一樣的。

有了前面的基礎(chǔ)，你完全可以自己寫出來了，所以我就不詳細(xì)分析了。我把代碼貼出來，你可以寫完之后對比一下。

public int bsearch7(int[] a, int n, int value) {
  int low = 0;
  int high = n - 1;
  while (low <= high) {
    int mid =  low + ((high - low) >> 1);
    if (a[mid] > value) {
      high = mid - 1;
    } else {
      if ((mid == n - 1) || (a[mid + 1] > value)) return mid;
      else low = mid + 1;
    }
  }
  return -1;
}

LeetCode-34-code

class Solution {
    public static int[] searchRange(int[] nums, int target) {
        int[] ans = { -1, -1 };
        if (nums == null || nums.length == 0) {
            return ans;
        }
        ans[0] = findFirst(nums, target);
        ans[1] = findLast(nums, target);
        return ans;
    }

    public static int findFirst(int[] arr, int num) {
        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        int mid = 0;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] < num) {
                L = mid + 1;
            } else if (arr[mid] > num) {
                R = mid - 1;
            } else {
                ans = mid;
                R = mid - 1;
            }
        }
        return ans;
    }

    public static int findLast(int[] arr, int num) {
        int L = 0;
        int R = arr.length - 1;
        int ans = -1;
        int mid = 0;
        while (L <= R) {
            mid = L + ((R - L) >> 1);
            if (arr[mid] < num) {
                L = mid + 1;
            } else if (arr[mid] > num) {
                R = mid - 1;
            } else {
                ans = mid;
                L = mid + 1;
            }
        }
        return ans;
    }
}

image-20210505201006194