剑指 Offer 53 - II. 0～n-1中缺失的数字(二分查找)

/** * 剑指 Offer 53 - II. 0～n-1中缺失的数字 * @author wsq * @date 2020/10/08 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 示例 1: 输入: [0,1,3] 输出: 2 示例 2: 输入: [0,1,2,3,4,5,6,7,9] 输出: 8 链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof */ package search; public class MissingNumber { /** * 二分查找，知道目标后使得右指针左移去寻找更小满足条件的位置 * @param nums * @return */ public int missingNumber(int[] nums) { int n = nums.length; int pos = n; int left = 0; int right = n - 1; int mid = -1; while(left <= right){ mid = (left + right) >> 1; if(nums[mid] != mid){ if(mid < pos){ pos = mid; } right = mid - 1; }else{ left = mid + 1; } } return pos; } public static void main(String[] args) { int[] nums = {0,1,2,3,4,5,6,7,9}; MissingNumber mn = new MissingNumber(); int ans = mn.missingNumber(nums); System.out.println(ans); } }