Part ONE: Four basic cases
1. Binary search without repeated numbers
Leetcode-cn.com/problems/bi…
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
int l = 0 , r = n-1;
while(l < r){
int mid = l + r + 1 >> 1;
if(nums[mid] > target) r = mid-1;
else l = mid;
}
return nums[l] == target ? l : -1; }}Copy the code2. Binary search for the first and last position with repeated numbers
Leetcode-cn.com/problems/fi…
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
int n = nums.length;
if(n == 0) return new int[] {-1, -1};
// find the first location
int l = 0 , r = n-1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] < target) l = mid+1;
else r = mid;
}
if(nums[l] ! = target)return new int[] {-1, -1};
else res[0] = l;
// Find the last location
l = 0;
r = n-1;
while(l < r){
int mid = l + r +1 >> 1;
if(nums[mid] > target) r = mid-1;
else l = mid;
}
res[1] = l;
returnres; }}Copy the code3. Search for the insertion position
Leetcode-cn.com/problems/se…
class Solution {
public int searchInsert(int[] nums, int target) {
int n = nums.length;
//1. Note that if the last number is less than target, the array length is returned
if (n == 0 || nums[n-1] < target) return n;
int l = 0 , r = n-1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] < target) l = mid + 1;
else r = mid;
}
returnl; }}Copy the code4. Square root of x (keep integer parts only)
class Solution {
public int mySqrt(int x) {
int l = 0 , r = x;
while(l < r){
int mid = l + r + 1 >> 1;
if(mid > x / mid) r = mid-1;
else l = mid;
}
returnl; }}Copy the code5. Look for repeated numbers
Leetcode-cn.com/problems/fi…
class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length;
// The range of values is further divided
int l = 0 , r = n-1;
while (l < r){
int mid = l+r >>1;
// Let's see how many numbers in the array are less than mid
int count = 0;
for (int num : nums){
if (num <= mid) count++;
}
// The number less than mid is greater than mid, indicating that it is on the left
if (count > mid) r = mid;
else l = mid+1;
}
returnl; }}Copy the code6. Implement Pow (x, n)
Leetcode-cn.com/problems/po…
class Solution {
public double myPow(double x, int n) {
double res = 1.0;
for(inti = n ; i ! =0 ; i /=2) {if(i % 2! =0) res = res * x;
x *= x;
}
return n < 0 ? 1/res : res; }}Copy the code7. Find the median of two sorted arrays
Leetcode-cn.com/problems/me…
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int n = nums1.length;
int m = nums2.length;
int l = (n + m + 1) /2;
int r = (n + m + 2) /2;
return (getK(nums1, 0 , n-1 , nums2 , 0 , m-1 , l) + getK(nums1 , 0 ,n-1 , nums2 ,0,m-1,r))/2.0;
}
// Get the KTH largest number from two positive ordinal groups
int getK(int[] nums1 , int s1 , int e1 , int[] nums2 , int s2 , int e2 , int k){
int len1 = e1 - s1 + 1;
int len2 = e2 - s2 + 1;
if(len1 > len2) return getK(nums2 , s2 , e2 , nums1 , s1 , e1 , k);
if(len1 == 0) return nums2[s2 + k -1];
if(k == 1) return Math.min(nums1[s1] , nums2[s2]);
int i = s1 + Math.min(len1 , k/2) -1; // Take half the value each time
int j = s2 + Math.min(len2 , k/2) -1;
// Each round removes the smaller half of the data set
if(nums1[i] > nums2[j]) return getK(nums1 , s1 ,e1 , nums2 ,j+1, e2 ,k-(j-s2+1));
else return getK(nums1, i+1 ,e1 , nums2 , s2 , e2 , k-(i-s1+1)); }}Copy the codePart two: Rotate the sort array
1. Find the minimum value in the rotation sort array (no duplicates)
Leetcode-cn.com/problems/fi…
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0 , r = n-1;
while(l < r){
int mid = l + r >> 1;
/ / 34512
if(nums[mid] > nums[r]) l = mid+1;
else r = mid;
}
returnnums[l]; }}Copy the code2. Find the minimum value in the rotation sort array (with duplicate values)
Leetcode-cn.com/problems/fi…
class Solution {
public int findMin(int[] nums) {
int n = nums.length;
int l = 0 , r = n-1;
while(l < r){
int mid = l + r >> 1;
if(nums[mid] > nums[r]) l = mid+1;
else if(nums[mid] < nums[r]) r = mid;
else r--;
}
returnnums[l]; }}Copy the code3. Find the specified value in the rotation sort array (no duplicate value)
Leetcode-cn.com/problems/se…
class Solution {
public int search(int[] nums, int target) {
int n = nums.length;
if(n == 0) return -1;
int l = 0 , r = n-1;
while(l < r){
int mid = l + r >> 1;
/ / 34512
if(nums[mid] > nums[r]){
if(target >= nums[l] && target <= nums[mid]) r = mid;
else l = mid+1;
}else{
/ / 561234
if(target > nums[mid] && target <= nums[r]) l = mid+1;
elser = mid; }}return nums[l] == target ? l : -1; }}Copy the codePart three: two dimensional matrix
1. Search a two-dimensional matrix
Leetcode-cn.com/problems/se…
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length; / / the number of rows
int n = matrix[0].length; / / the number of columns
int l = 0 , r = m *n -1;
while(l < r){
int mid = l + r + 1 >> 1;
// Convert a one-dimensional array to a two-dimensional coordinate
if(matrix[mid / n][ mid % n] > target) r = mid-1;
else l = mid;
}
returnmatrix[l/n][l%n] == target; }}Copy the code2. Search the two-dimensional matrix 2
Leetcode-cn.com/problems/se…
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length; / / the number of rows
int n = matrix[0].length; / / the number of columns
int i = 0 , j = n-1;
while(i <= m-1 && j >= 0) {if(matrix[i][j] > target) j--;
else if(matrix[i][j] < target) i++;
else return true;
}
return false; }}Copy the codeThe KTH smallest number in an ordered matrix
Leetcode-cn.com/problems/kt…
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int row = matrix.length;
int col = matrix[0].length;
int l = matrix[0] [0];
int r = matrix[row-1][col-1];
while(l < r){
int mid = l + r >> 1;
int count = findCount(matrix, mid , row ,col); // Find the number of <= mid in the matrix
if(count < k) l = mid + 1;
else r = mid;
}
return l;
}
/ / 1 5 and 9
/ / 10 11 12 13
/ / 12 13 to 15
int findCount(int[][] matrix , int mid , int row , int col){
int i = row-1 , j = 0;
int count = 0;
while(i >= 0 && j <= col-1) {if(matrix[i][j] <= mid){
count += i+1; // the JTH column has I +1 <=mid
j++;
}else i--;// The value of column j is greater than mid
}
returncount; }}Copy the code