【問題描述】[中等]

統計一個數字在排序數組中出現的次數。 示例 1:輸入: nums = [5,7,7,8,8,10], target = 8 輸出: 2 示例 2:輸入: nums = [5,7,7,8,8,10], target = 6 輸出: 0

【解答思路】

1. 暴力法/遍歷

時間復雜度：O(N) 空間復雜度：O(1)

public int search(int[] nums, int target) {int count = 0;for(int num : nums){if(num == target){count++;}}return count;}

2. 二分法

有序數組 分別找到 taret 的左右邊界 right - left +1
時間復雜度：O(logN) 空間復雜度：O(1)

public class Solution {public int search(int[] nums, int target) {int len = nums.length;if (len == 0) {return 0;}int firstPosition = findFirstPosition(nums, target);if (firstPosition == -1) {return 0;}int lastPosition = findLastPosition(nums, target);return lastPosition - firstPosition + 1;}private int findFirstPosition(int[] nums, int target) {int len = nums.length;int left = 0;int right = len - 1;while (left < right) {int mid = left + (right - left) / 2;// 注意這樣寫，可以從左邊收縮待搜索區間的范圍，進而找到第一次出現的位置if (nums[mid] < target) {// mid 以及 mid 左邊都不是，下一輪搜索區間在 [mid + 1, right]left = mid + 1;} else {right = mid;}}if (nums[left] == target) {return left;}return -1;}private int findLastPosition(int[] nums, int target) {int len = nums.length;int left = 0;int right = len - 1;while (left < right) {int mid = left + (right - left + 1) / 2;// 注意這樣寫，可以從右邊收縮待搜索區間的范圍，進而找到最后一次出現的位置if (nums[mid] > target) {// mid 以及 mid 右邊都不是，下一輪搜索區間在 [left, mid - 1]right = mid - 1;} else {left = mid;}}return left;} }

【總結】

1.二分查找思路

2.排除法思考二分法

1、確定搜索區間初始化時候的左右邊界，有時需要關注一下邊界值。在初始化時，有時把搜索區間設置大一點沒有關系，但是如果恰好把邊界值排除在外，再怎么搜索都得不到結果。

2、無條件寫上 while (left < right) ，表示退出循環的條件是 left == right，對于返回左右邊界就不用思考了，因此此時它們的值相等；

3、先寫下取整的中間數取法，然后從如何把 mid 排除掉的角度思考 if 和 else 語句應該怎樣寫。

（這里建議寫兩個注釋。）

• 一般而言，我都會把**“什么時候不是目標元素”**作為注釋寫在代碼中，提醒自己要判斷正確，這一步判斷非常關鍵，直接影響到后面的代碼邏輯。
• 然后接著思考 mid 不是解的情況下，mid 的左右兩邊可能存在解，把下一輪搜索的區間范圍作為注釋寫進代碼里，進而在確定下一輪搜索區間邊界的收縮行為時，不容易出錯。

if 有把握寫對的情況下，else 就是 if 的反面，可以不用思考，直接寫出來。

** 說明：這種思考方式，就正正好把待搜索區間從邏輯上分成兩個區間，一個區間不可能存在目標元素，進而在另一個區間里繼續搜索，更符合“二分”的語義。**

4、根據 if else 里面寫的情況，看看是否需要修改中間數下取整的行為。


上面已經說了，只有看到 left = mid 的時候，才需要調整成為上取整，記住這一點即可，我因為剛開始不理解這種寫法，遇到很多次死循環，現在已經牢記在心了。

5、退出循環的時候，一定有 left == right 成立。有些時候可以直接返回 left （或者 right，由于它們相等，后面都省略括弧）或者與 left 相關的數值，有些時候還須要再做一次判斷，判斷 left 與 right 是否是我們需要查找的元素，這一步叫“后處理”。

// 有可能區間內不存在目標元素，因此還需做一次判斷if (nums[left] == target) {return left;}return -1; public int searchInsert(int[] nums, int target) {int len = nums.length;if (len == 0) {return 0;}int left = 0;// 因為有可能數組的最后一個元素的位置的下一個是我們要找的，故右邊界是 lenint right = len;while (left < right) {int mid = (left + right) >>> 1;// 小于 target 的元素一定不是解if (nums[mid] < target) {// 下一輪搜索的區間是 [mid + 1, right]left = mid + 1;} else {right = mid;}}return left;}

轉載鏈接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/solution/er-fen-cha-zhao-fa-zhao-dao-di-yi-ci-chu-xian-de-w/

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的[剑指offer]面试题第[53-1]题[JAVA][在排序数组中查找数字-1][二分法][暴力法]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。