153. Find Minimum in Rotated Sorted Array(leetcode, binary search)

╰+哭是因爲堅強的太久メ 2021-09-30 14:38 185阅读 0赞

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/

leetcode 的题目，binary search 的变形。去在rotated array里找最小值。

Idea：分析binary search 三种cases：

1. nums\[mid\] > nums\[r\]: remove the left part: l = mid+1          e.g. 2 3 4 5 1 2

2. nums\[mid\] < nums\[l\] && nums\[mid\] < nums\[r\]: h = mid       e.g. 5 6 1 2 3 4

3. nums\[mid\] <nums\[r\] && nums\[mid\] > nums\[l\]: h = mid                e.g. 1 2 3 4 5 6

Combing the 2nd and 3rd case.

二分查找有点难， left 和 right的分析， 在合适 的时候break while loop.

1 public int findMin(int[] nums) {
     2         if(nums.length==0) return 0;
     3         int l = 0, r = nums.length-1; // [)
     4         while(l < r){
     5             int mid = l+(r-l)/2;
     6             if(nums[mid]>nums[r]){
     7                 l = mid+1;//remove 
     8             }else
     9                 r = mid;
    10         }
    11         return nums[l];
    12     }

二分查找还要继续总结一个模板。

to be continued。。。。。

转载于:https://www.cnblogs.com/stiles/p/153L.html

发表评论取消回复

表情：

评论列表（有 0 条评论，185人围观）

还没有评论，来说两句吧...

相关阅读

相关 Find Minimum in Rotated Sorted Array II--LeetCode

> Follow up for "Find Minimum in Rotated Sorted Array": > What if duplicates are allow

￡神魔★判官ぃ/ 2022年08月07日 12:58/ 0 赞/ 132 阅读

相关 LeetCode154—Find Minimum in Rotated Sorted Array II

原题 [原题链接][Link 1] > Follow up for “Find Minimum in Rotated Sorted Array”: > What i

逃离我推掉我的手/ 2022年07月15日 12:26/ 0 赞/ 77 阅读

相关 LeetCode154—Find Minimum in Rotated Sorted Array II

原题 [原题链接][Link 1] > Follow up for “Find Minimum in Rotated Sorted Array”: > What i

心已赠人/ 2022年07月15日 12:26/ 0 赞/ 90 阅读

相关 LeetCode153—Find Minimum in Rotated Sorted Array

原题 [原题链接][Link 1] > Suppose a sorted array is rotated at some pivot unknown to you b

不念不忘少年蓝@/ 2022年07月15日 10:12/ 0 赞/ 89 阅读

相关 [Leetcode]153. Find Minimum in Rotated Sorted Array

Obviously this question can be solved within `O(n)` time by traversing the whole array a

怼烎@/ 2022年07月12日 09:22/ 0 赞/ 138 阅读

相关 leetcode 153. Find Minimum in Rotated Sorted Array 旋转数组（不重复）+二分查找

Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor

Myth丶恋晨/ 2022年06月08日 06:28/ 0 赞/ 130 阅读

相关 153. Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you befor

太过爱你忘了你带给我的痛/ 2022年03月07日 05:04/ 0 赞/ 158 阅读

相关 [LeetCode] Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand. (i.e., `0 1

朴灿烈づ我的快乐病毒、/ 2021年12月03日 07:29/ 0 赞/ 118 阅读

相关 LeetCode-153 Find Minimum in Rotated Sorted Array

题目描述 Suppose an array sorted in ascending order is rotated at some pivot unknown to you

爱被打了一巴掌/ 2021年11月16日 23:48/ 0 赞/ 180 阅读

相关 153. Find Minimum in Rotated Sorted Array(leetcode, binary search)

https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/ leetcod

╰+哭是因爲堅強的太久メ/ 2021年09月30日 14:38/ 0 赞/ 186 阅读