LeetCode算法题–二分法javaManigoat的博客-

0153寻找旋转排序数组的最小值(无重复元素)

假设按照升序排序的数组在预先未知的某个点上进行了旋转。请找出其中最小的元素。你可以假设数组中不存在重复元素。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

int findMin(vector<int>& nums) { int left = 0; int right = nums.size() - 1; while (left < right) { int mid = left + (right - left) / 2; //不存在重复元素；nums[mid]与nums[right]必不等 if (nums[mid] > nums[right]) {                       left = mid + 1; } else {                                            right = mid; } } return nums[left];//nums[right]也可以,此时left==right } 

0154寻找旋转排序数组的最小值(有重复元素)

注意数组中可能存在重复的元素。

public int findMin(int[] nums) { /**     和 I 的做法类似, 都是二分法, 每次进入无序的那部分找出最小值     但是由于有重复值的情况, 需要加入 mid 元素等于 hi 元素的情况     此时应该将 hi 减 1 防止重复数字是最小元素     **/ int l = 0, h = nums.length-1; while(l < h) { int mid = l+(h-l)/2; if(nums[mid] > nums[h])             l = mid+1; else if(nums[mid] < nums[h])             h = mid; else             h--; } return nums[l]; } 

0069平方根—实现int sqrt(int x)函数

JAVA

public static int mySqrt(int x) { if (x < 2) return x; long num; int pivot, left = 2, right = x / 2; while (left <= right) {         pivot = left + (right - left) / 2;         num = (long)pivot * pivot; if (num > x) right = pivot - 1; else if (num < x) left = pivot + 1; else return pivot; } return right; } 

C++

int mySqrt(int x) { int l = 0, r = x; while (l <= r) { int mid = l + (r - l) / 2; long long num=(long long)mid * mid; if (num<x) {             l = mid + 1; }else if(num>x){             r = mid - 1; }else{ return mid; } } return r; } 

0035搜索插入位置

JAVA

public int searchInsert(int[] nums, int target) { int l = 0, h = nums.length-1; while(l<=h){ int mid = l+(h-l)/2; //防止(h+l)/2加法溢出 if(nums[mid]==target) return mid; else if(nums[mid]>target)             h = mid-1; else             l = mid+1; } return l; } 

C++

int searchInsert(vector<int>& nums, int target) { int l=0; int r= nums.size()-1; while(l<=r){ int mid=l+(r-l)/2; if(nums[mid]>target){       r=mid-1; }else if(nums[mid]<target){    l=mid+1; }else{ return mid; } } return l; }