【算法】【优选算法】二分查找算法（下）_设有序表有100个元素,用二分法查找某个元素时,最大比较次数是 。

目录

• 一、852.⼭脉数组的峰顶索引
• • 1.1 二分查找
  • 1.2 暴力枚举
• 二、162.寻找峰值
• • 2.1 二分查找
  • 2.2 暴力枚举
• 三、153.寻找旋转排序数组中的最⼩值
• • 3.1 二分查找
  • 3.2 暴力枚举
• 四、LCR 173.点名
• • 4.1 二分查找
  • 4.2 哈希表
  • 4.3 暴力枚举
  • 4.4 位运算
  • 4.5 数学（求和）

一、852.⼭脉数组的峰顶索引

题目链接：852.⼭脉数组的峰顶索引
题目描述：

题目解析：

• 给我们一个数组，元素是先递增在递减的，让我们返回最大元素下标。

1.1 二分查找

解题思路：

• 我们这个数组本来就是一个被天然分成两段，递增区间和递减区间，的数据，天然使用二分查找的题。
• 当mid的元素小于后一个元素的时候，mid在递增区间，所以left = mid + 1。
• 当mid的元素大于后一个元素的时候，mid在递减区间，所以right = mid。

解题代码：

//时间复杂度：O(logN)//空间复杂度：O(1)class Solution { public int peakIndexInMountainArray(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)class Solution { public int peakIndexInMountainArray(int[] arr) { for(int i = 1; i < arr.length - 1; i++) { if(arr[i] > arr[i-1] && arr[i] > arr[i+1]) return i; } return 0; }}

二、162.寻找峰值

题目链接：162.寻找峰值
题目描述;

题目解析：

• 给我们的数组是，递增递减反复进行，让我们找到其中一个峰值的下标。
• 数组可能是这几个情况：1 . /\\/\\/\\ ，2. / ，3. \\

2.1 二分查找

解题思路：

• 其实我们可以将数组分为，有要求峰值和没有要求峰值两段，因为给了峰值不等于下一个元素。
• 所以当mid小于下一个元素的时候，mid就是在没有要求峰值那段，left = mid+1。
• 当mid大于下一个元素的时候，mid就是在有峰值那段，right = mid

解题代码：

//时间复杂度：O(logN)//空间复杂度：O(1)class Solution { public int findPeakElement(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)class Solution { public int findPeakElement(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 ]为界限：class Solution { public int findMin(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 ]为界限：class Solution { public int findMin(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)class Solution { public int findMin(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)class Solution { public int takeAttendance(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)class Solution { public int takeAttendance(int[] records) { int[] hash = new int[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; } return 0; }}

4.3 暴力枚举

解题思路：

• 直接遍历数组，当出现第一个下标和元素不相等的直接返回元素减一即可。
• 遍历完数组还是没找到，证明是0到n中n不在数组中。

解题代码：

//时间复杂度：O(n)//空间复杂度：O(1)class Solution { public int takeAttendance(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)class Solution { public int takeAttendance(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)class Solution { public int takeAttendance(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; }}