Leetcoe高频题(八) 我就不信邪了 LeetCode 二分法

二分法

35. 搜索插入位置162. 寻找峰值NC48 二分查找NC105 转动过得有序数组中寻找目标值

---

35. 搜索插入位置

class Solution { public int searchInsert(int[] nums, int target) { int high = nums.length - 1; int low = 0; while ( low <= high ) { int mid = (low + high ) >>1; if ( target > nums[mid]) { low = mid + 1; }else if ( target < nums[mid]) { high = mid - 1; }else { return mid; } } return low; } }

162. 寻找峰值

class Solution { public int findPeakElement(int[] nums) { if(nums.length==0||nums==null) return -1; if(nums.length==1) return 0; int l=0; int r=nums.length-1; while(l<r){ int mid=(r-l)/2+l; if(nums[mid]<nums[mid+1]) l=mid+1; else r=mid; } return l; } }

NC48 二分查找

import java.util.*; public class Solution { public int upper_bound_ (int n, int v, int[] a) { int i=0; int j=n-1; int index=n+1; if (v > a[n - 1]) return n + 1; //如果最大值小于查找值则直接返回 // [2,3,4] 1 // [2,3,4,4,5] 4 while(i<j){ int mid=(i+j)/2; if(a[mid]>=v){ j=mid; } else{ i=mid+1; } } return i+1; } }

NC105 转动过得有序数组中寻找目标值

import java.util.*; public class Solution { /** * * @param A int整型一维数组 * @param target int整型 * @return int整型 */ public int search (int[] A, int target) { // write code hereint int len = A.length; int left = 0; int right = len-1; while(left <= right) { int middle = (right+left)>>1; if(A[middle] == target) return middle; if(A[left] <= A[middle]) /// left side is sorted { if(A[left] <= target && target < A[middle]) right = middle-1;//[3,5,7,8,1,2] 5 else left = middle+1;//[6,7,1,2,3,4,5] 3 } else /// right side is sorted { if(A[middle] < target && target <= A[right]) left = middle+1; //[6,7,1,2,3,4,5] 3 else right = middle-1;//[3,5,7,8,1,2] 5 } } return -1; } }