【算法】【优选算法】二分查找算法（下）
目录
一、852.⼭脉数组的峰顶索引
题目链接：852.⼭脉数组的峰顶索引
题目描述：
题目解析：
- 给我们一个数组，元素是先递增在递减的，让我们返回最大元素下标。
1.1 二分查找
解题思路：
- 我们这个数组本来就是一个被天然分成两段，递增区间和递减区间，的数据，天然使用二分查找的题。
- 当mid的元素小于后一个元素的时候，mid在递增区间，所以left = mid + 1。
- 当mid的元素大于后一个元素的时候，mid在递减区间，所以right = mid。
解题代码：
//时间复杂度：O(logN)//空间复杂度：O(1)classSolution{publicintpeakIndexInMountainArray(int[] arr){int left =0;int right = arr.length-1;while(left < right){int mid = left +(right - left)/2;if(arr[mid]< arr[mid+1]) left = mid +1;else right = mid;}return left;}}1.2 暴力枚举
解题思路：
- 直接使用for循环遍历数组，该下标元素大于前面和后面元素，返回下标。
- 因为这个数组一定是一个山脉数组，所以不用管数组头和尾。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicintpeakIndexInMountainArray(int[] arr){for(int i =1; i < arr.length -1; i++){if(arr[i]> arr[i-1]&& arr[i]> arr[i+1])return i;}return0;}}二、162.寻找峰值
题目链接：162.寻找峰值
题目描述;
题目解析：
- 给我们的数组是，递增递减反复进行，让我们找到其中一个峰值的下标。
- 数组可能是这几个情况：1 . /\/\/\ ，2. / ，3. \
2.1 二分查找
解题思路：
- 其实我们可以将数组分为，有要求峰值和没有要求峰值两段，因为给了峰值不等于下一个元素。
- 所以当mid小于下一个元素的时候，mid就是在没有要求峰值那段，left = mid+1。
- 当mid大于下一个元素的时候，mid就是在有峰值那段，right = mid
解题代码：
//时间复杂度：O(logN)//空间复杂度：O(1)classSolution{publicintfindPeakElement(int[] nums){int left =0;int right = nums.length -1;while(left < right){int mid = left +(right - left)/2;if(nums[mid]< nums[mid +1]) left = mid +1;else right = mid;}return left;}}2.2 暴力枚举
解题思路：
- 直接转变为求数组最大值下标，遍历数组即可。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicintfindPeakElement(int[] nums){int ret =0;for(int i =0; i < nums.length; i++){if(nums[i]> nums[ret]) ret = i;}return ret;}}三、153.寻找旋转排序数组中的最⼩值
题目链接：153.寻找旋转排序数组中的最⼩值
题目描述：
题目解析：
- 数组旋转一次就代表将数组尾元素放在数组头。
- 给我们一个原来升序的数组，旋转多次后，找到数组中最小元素下标。
- 数组中元素各不相同。
数组会是下面这种状态或者一个完全递增的状态
3.1 二分查找
解题思路：
- 我们这个数组本来就是已经是被分成两段了的。
- 我们可以使用nums[ 0 ]或者nums[ nums.length - 1 ]来当分界线。
- 使用nums[ nums.length - 1 ]为界限：
- mid元素大于等于界限时，在数组段1，所以left = mid + 1。
- mid元素小于界限的时候，在数组段2，所以right = mid。
- 使用nums[ 0 ]为界限：
- mid元素大于等于界限时，在数组段1，所以left = mid + 1。
- mid元素小于界限的时候，在数组段2，所以right = mid。
- 考虑数组完全递增时，nums[0]才是最小值。
解题代码：
//时间复杂度：O(logN)//空间复杂度：O(1)//使用nums[ nums.length - 1 ]为界限：classSolution{publicintfindMin(int[] nums){int left =0;int right = nums.length -1;while(left < right){int mid = left +(right - left)/2;if(nums[mid]< nums[nums.length-1]) right = mid;else left = mid +1;}return nums[left];}}//使用nums[ 0 ]为界限：classSolution{publicintfindMin(int[] nums){int left =0;int right = nums.length -1;while(left < right){int mid = left +(right - left)/2;if(nums[mid]>= nums[0]) left = mid +1;else right = mid;}if(nums[0]< nums[left]) left =0;return nums[left];}}3.2 暴力枚举
解题思路;
- 直接循环遍历数组找最小值即可。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicintfindMin(int[] nums){int ret = nums[0];for(int i =0; i < nums.length; i++){if(nums[i]< ret) ret = nums[i];}return ret;}}四、LCR 173.点名
题目链接：LCR 173.点名
题目描述：
题目解析：
- 给你一个长度为n数组，这个数组中有0到n中的数，按升序排列，找出数组在0到n中不含有的数。
4.1 二分查找
解题思路：
- 这个数组分为这样两段，一段是下标与元素值相同的，一段是下标是元素值减1。
- 所以当mid元素等于mid的时候，落在第一段，left = mid + 1;
- 当mid元素不等于mid的时候，落在第二段，right = mid。
解题代码：
//时间复杂度：O(logN)//空间复杂度：O(1)classSolution{publicinttakeAttendance(int[] records){int left =0;int right = records.length;while(left < right){int mid = left +(right - left)/2;if(records[mid]== mid) left = mid +1;else right = mid;}return left;}}4.2 哈希表
解题思路：
- 借助一个数组来标记0到n中出现过的元素。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(n)classSolution{publicinttakeAttendance(int[] records){int[] hash =newint[records.length +1];for(int i =0; i < records.length; i++){ hash[records[i]]++;}for(int i =0; i < hash.length; i++){if(hash[i]==0)return i;}return0;}}4.3 暴力枚举
解题思路：
- 直接遍历数组，当出现第一个下标和元素不相等的直接返回元素减一即可。
- 遍历完数组还是没找到，证明是0到n中n不在数组中。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicinttakeAttendance(int[] records){for(int i =0; i < records.length; i++){if(records[i]!= i)return records[i]-1;}return records.length;}}4.4 位运算
解题思路：
- 直接使用一个变量来将0到n的数全部异或。
- 在于数组元素进行异或。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicinttakeAttendance(int[] records){for(int i =0; i < records.length; i++){if(records[i]!= i)return records[i]-1;}return records.length;}}4.5 数学（求和）
解题思路：
- 直接先将0到n的和求出来。
- 在减去数组中的元素即可。
解题代码：
//时间复杂度：O(n)//空间复杂度：O(1)classSolution{publicinttakeAttendance(int[] records){int n = records.length;int ret =(n*(n+1))/2;for(int i =0; i < records.length; i++){ ret = ret - records[i];}return ret;}}
