LeetCode 每周算法 7(二分查找)
二分查找算法:
class Solution {
public : int searchInsert ( vector< int > & nums, int target) { int left = 0 , right = nums. size ( ) - 1 ; while ( left <= right) { int mid = ( left + right) / 2 ; if ( nums[ mid] < target) { left = mid + 1 ; } else { right = mid - 1 ; } } return left; }
} ;
class Solution {
public : bool searchMatrix ( vector< vector< int >> & matrix, int target) { int m = matrix. size ( ) ; int n = matrix[ 0 ] . size ( ) ; int left = 0 , right = m * n - 1 ; while ( left <= right) { int mid = ( left + right) / 2 ; int x = mid / n; int y = mid % n; if ( matrix[ x] [ y] < target) { left = mid + 1 ; } else if ( matrix[ x] [ y] > target) { right = mid - 1 ; } else { return true ; } } return false ; }
} ;
class Solution {
public : int binarySearch ( vector< int > & nums, int target, bool lower) { int left = 0 , right = ( int ) nums. size ( ) - 1 , ans = ( int ) nums. size ( ) ; while ( left <= right) { int mid = ( left + right) / 2 ; if ( nums[ mid] > target || ( lower && nums[ mid] == target) ) { right = mid - 1 ; ans = mid; } else { left = mid + 1 ; } } return ans; } vector< int > searchRange ( vector< int > & nums, int target) { int leftIdx = binarySearch ( nums, target, true ) ; int rightIdx = binarySearch ( nums, target, false ) - 1 ; if ( leftIdx <= rightIdx && rightIdx < nums. size ( ) && nums[ leftIdx] == target && nums[ rightIdx] == target) { return vector< int > { leftIdx, rightIdx} ; } return vector< int > { - 1 , - 1 } ; }
} ;
class Solution {
public : int search ( vector< int > & nums, int target) { int n = ( int ) nums. size ( ) ; if ( ! n) { return - 1 ; } if ( n == 1 ) { return nums[ 0 ] == target ? 0 : - 1 ; } int l = 0 , r = n - 1 ; while ( l <= r) { int mid = ( l + r) / 2 ; if ( nums[ mid] == target) return mid; if ( nums[ 0 ] <= nums[ mid] ) { if ( nums[ 0 ] <= target && target < nums[ mid] ) { r = mid - 1 ; } else { l = mid + 1 ; } } else { if ( nums[ mid] < target && target <= nums[ n - 1 ] ) { l = mid + 1 ; } else { r = mid - 1 ; } } } return - 1 ; }
} ;
class Solution {
public : int findMin ( vector< int > & nums) { int left = 0 ; int right = nums. size ( ) - 1 ; while ( left < right) { int mid = left + ( right - left) / 2 ; if ( nums[ mid] < nums[ right] ) { right = mid; } else { left = mid + 1 ; } } return nums[ left] ; }
} ;
class Solution {
public : int getKthElement ( const vector< int > & nums1, const vector< int > & nums2, int k) { int m = nums1. size ( ) ; int n = nums2. size ( ) ; int index1 = 0 , index2 = 0 ; while ( true ) { if ( index1 == m) { return nums2[ index2 + k - 1 ] ; } if ( index2 == n) { return nums1[ index1 + k - 1 ] ; } if ( k == 1 ) { return min ( nums1[ index1] , nums2[ index2] ) ; } int newIndex1 = min ( index1 + k / 2 - 1 , m - 1 ) ; int newIndex2 = min ( index2 + k / 2 - 1 , n - 1 ) ; int pivot1 = nums1[ newIndex1] ; int pivot2 = nums2[ newIndex2] ; if ( pivot1 <= pivot2) { k -= newIndex1 - index1 + 1 ; index1 = newIndex1 + 1 ; } else { k -= newIndex2 - index2 + 1 ; index2 = newIndex2 + 1 ; } } } double findMedianSortedArrays ( vector< int > & nums1, vector< int > & nums2) { int totalLength = nums1. size ( ) + nums2. size ( ) ; if ( totalLength % 2 == 1 ) { return getKthElement ( nums1, nums2, ( totalLength + 1 ) / 2 ) ; } else { return ( getKthElement ( nums1, nums2, ( totalLength + 1 ) / 2 ) + getKthElement ( nums1, nums2, totalLength / 2 + 1 ) ) / 2.0 ; } }
} ;