『leetcode』二分搜索

本次题解包括：

4 Median of Two Sorted Arrays
33 Search in Rotated Sorted Array
34 Search for a Range
35 Search Insert Position
69 Sqrt(x)
74 Search a 2D Matrix
81 Search in Rotated Sorted Array II
153 Find Minimum in Rotated Sorted Array
154 Find Minimum in Rotated Sorted Array II
240 Search a 2D Matrix II

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:
1
2
3
4
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
1
2
3
4
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

题目地址：leetcode Median of Two Sorted Arrays

题意：

给定两个排好序的数组，求它们的中位数。

思路：

首先，求中位数需要注意奇数偶数的情况。

方法一

设nums1长度为m，nums2的长度为n，将问题转化为在两个排好序的数组中找第k = (m + n + 1) / 2 小的元素（若总数是偶数还需要找第k+1大的元素）。

为了方便说明，假设 m<=n

每次a_m= min(m, k/2)，b_mid = k - a_m，然后比较A中第a_m个元素和B中第b_m个元素，即A[a_m - 1]和B[b_m - 1]，

若A[a_m - 1] < B[b_m - 1]，则说明第k小的元素不可能出现在A中的前a_m个，也不可能出现在B中的b_m之后。即在A[a_m:]，B[:b_m + 1]中查找第k - a_m元素。（因为a_m + b_m = k，不可能出现在A的a_m个的话，B中的前b_m个元素已经足够k-a_m个了）
若A[a_m - 1] >B[b_m - 1]，则说明第k小的元素不可能出现在B中的前b_m个，也不会再A中的a_m之后，因此，在A[a_m + 1]，B[b_m:]中查找k - b_m元素
若相等，则找到了

复杂度O(log(m + n))

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """

        def find_k_th(k, a, b):
            m, n = len(a), len(b)
            if m > n:
                return find_k_th(k, b, a)
            if m == 0:
                return b[k - 1]
            if k == 1:
                return min(a[0], b[0])

            a_mid = min(k >> 1, m)
            b_mid = k - a_mid
            if a[a_mid - 1] < b[b_mid - 1]:
                return find_k_th(k - a_mid, a[a_mid:], b[:b_mid + 1])
            elif a[a_mid - 1] > b[b_mid - 1]:
                return find_k_th(k - b_mid, a[:a_mid + 1], b[b_mid:])
            else:
                return a[a_mid - 1]

        m, n = len(nums1), len(nums2)
        k = (m + n + 1) >> 1
        ans = find_k_th(k, nums1, nums2)
        if (m + n) & 1: return ans
        ans = ans + find_k_th(k + 1, nums1, nums2)
        return ans / 2.0

方法二：

同样假设m <= n，我们需要找到的是一个i和一个j，这两个下标分别将两个数组划分为左右两部分：

1
2
3

      left_part                  right_part
A[0], A[1], ..., A[i-1]    A[i], A[i+1], ..., A[m-1]
B[0], B[1], ..., B[j-1]    B[j], B[j+1], ..., B[n-1]

当然i未必和j相等。若能找到一个这样的i和j，满足：

i + j = (m + n + 1) / 2
并且a[i-1] < a[j]， a[j-1] < a[i]

这两个条件使得a[i - 1], 和b[j - 1]恰好为在中间的数，谁大谁就是中位数，若m + n为，偶数，则还要考虑a[i]和a[j]中较小的数。（i=0或j=0或i = m或j = n的特殊情况之后讨论）

因此，可以二分枚举i，起始范围left= 0, right = m，则j = (m + n + 1) / 2 - i，

若a[i] < b[j - 1]，则说明i太小，要增大i，left = i + 1
若a[i - 1] > b[j]，说明i太大，要减小i，right = i - 1
否则找到了i和j的正确位置，看m + n是奇数的话直接返回max(a[i - 1], b [j- 1])即可，否则为(max(a[i - 1], b [j- 1]) + min(a[i], b[j])) / 2

现在讨论边界情况：

i = 0时，此时j = (m + n + 1) / 2，此时即可假设a[i-1]必定小于b[j]，只需要看 a[i] > b[j -1]即可
i = m时，此时j = (n - m + 1) / 2 > 0，也可以说a[i] > b[j - 1]，只需要看a[i - 1] < b[j]即可
j = 0和j = n同理

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        if(m > n) return findMedianSortedArrays(nums2, nums1);
        
        int left = 0, right = m, half_len = (m + n + 1) >> 1;
        while(left <= right){
            int i = (left + right) >> 1;
            int j = half_len - i;
            if(i > 0 && nums1[i - 1] > nums2[j])
                right = i - 1;
            else if(i < m && j > 0 && nums1[i] < nums2[j - 1])
                left = i + 1;
            else{
                int left_max = i != 0? nums1[i - 1] : INT_MIN;
                if(j != 0 && nums2[j - 1] > left_max)
                    left_max = nums2[j - 1];
                if((m + n) & 1) 
                    return left_max;
                
                int right_min = i != m? nums1[i] : INT_MAX;
                if(j != n && nums2[j] < right_min)
                    right_min = nums2[j];
                return (left_max + right_min) / 2.0;
            }
        }
        return -1.0;
    }
};

33. Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

题目地址：leetcode Search in Rotated Sorted Array

题目大意给定一个排好序，但是经过旋转的数组（如0 1 2 4 5 6 7 变为 4 5 6 7 0 1 2），且该数组元素唯一。给定一个数，求其出现的下标，若不存在，返回-1

思路：

也是二分搜索。一个trick是A[L] <= A[mid]说明[L,mid]为升序

方法一 O(log n)

注意两个等于号：

搜索l <= r，这里二分是左右边界都可以取值，因此需要取等于号，否则当只有一个数的时候就退出了
当l == mid 的时候需要进的逻辑是哪个？如[3, 1]这个case
- 如果进的是nums[mid] < nums[r]里的分支，就会有问题，因为[mid, r]并非完全升序
- 因此一定要写上nums[l] <= nums[mid]，如果觉得等于号难以理解，可以改成if (nums[l] < nums[mid] || l == mid)

C++

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;
        int l = 0;
        int r = nums.size() - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] == target) return mid;

            if (nums[l] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            } else { // nums[mid] < nums[r]
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return -1;
    }
};

Python

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) >> 1
            if nums[mid] == target: return mid
            
            if nums[left] <= nums[mid]:
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            else:
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
        return -1

以前写的 O(log n)

若nums[mid] == target 没什么好说的，返回mid
若nums[mid] < target
- 若nums[mid] < nums[right] && target <= nums[right] nums[mid] > nums[right]
  - 即右边有序且target在右边的范围内或者右边非有序则 left = mid + 1
  - 因为nums[mid] < target 所以若右边非有序，则左边一定有序，target一定大于左边的所有元素，只能在右边
- 否则right = mid - 1
target < nums[mid]
- 若nums[left] < nums[mid] && nums[left] <=target
  - 即左边有序且target在左边的范围内或者左边无序列 right = mid - 1;
  - 因为target < nums[mid] ，若左边无序则nums[mid]小于右边的所有元素，只能在左边。
- 否则left = mid + 1

C++

class Solution {
public:
	int search(vector<int>& nums, int target) {
		int left = 0, right = nums.size() - 1;
		while (left <= right) {
			int mid = (left + right) >> 1;
			if (nums[mid] == target)
				return mid;
			else if (nums[mid] < target) {
				if (nums[mid] < nums[right] && target <= nums[right] ||
					nums[mid] > nums[right])
					left = mid + 1;
				else
					right = mid - 1;
			}
			else { // if (target < nums[mid])
				if (nums[left] < nums[mid] && target >= nums[left] ||
					nums[left] > nums[mid])
					right = mid - 1;
				else
					left = mid + 1;
			}
		}
		return -1;
	}
};

34. Search for a Range

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4].

题目地址：leetcode Search for a Range

题目大意：给定一个数组A，和一个要查找的数target,返回数组A中出现的位置（第一次出现和最后一次出现），如果不存在，为-1，-1

思路：就是二分搜索找上下界。（可以先做35题）水~

C++

class Solution {
	int binary_search(bool left, const vector<int> &nums, const int target) {
		int L = 0, R = nums.size();
		while (L < R) {
			int mid = (L + R) >> 1;
			if (left ? nums[mid] < target : nums[mid] <= target)
				L = mid + 1;
			else
				R = mid;
		}
		return L;
	}

public:
	vector<int> searchRange(vector<int>& nums, int target) {
		vector<int> ans{ -1, -1 };
		int L = binary_search(true, nums, target);
		if (L == nums.size() || nums[L] != target) return ans;
		int R = binary_search(false, nums, target);
		ans = { L, R - 1 };
		return ans;
	}
};

Python

class Solution(object):
    def binary_search(self, left, nums, target):
        L, R = 0, len(nums)
        while L < R:
            mid = (L + R) >> 1
            if nums[mid] < target or (not left and nums[mid] <= target):
                L = mid + 1
            else:
                R = mid
        return L
    
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        L = self.binary_search(True, nums, target)
        if L == len(nums) or nums[L] != target: return [-1, -1]
        R = self.binary_search(False, nums, target)
        return [L, R - 1]

35 . Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0

题目地址：leetcode Search Insert Position

题目大意: 给定一个排好序的数组和一个数，返回这个数插入的位置。

思路：水~二分

C++

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int L = 0, R = nums.size(); 
        while (L < R) { 
            int mid = (L + R) >> 1; 
            if (nums[mid] < target) 
                L = mid + 1; 
            else 
                R = mid; 
        } 
        return L;
    }
};

Python

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        L, R = 0, len(nums)
        while L < R:
            mid = (L + R) >> 1
            if nums[mid] < target:
                L = mid + 1
            else:
                R = mid
        return L

69. Sqrt(x)

Implement int sqrt(int x).

Compute and return the square root of x.

题目地址：leetcode Sqrt(x)

题目大意：实现根号n的计算

思路：

方法一：二分法

C++要用long long 防止越界，py弱类型好处体现出来了。。

C++

class Solution {
public:
	int mySqrt(int x) {
		long long l = 0, r = x >> 1;
		while (l <= r) {
			long long mid = l + ((r - l) >> 1);
			long long mul = mid * mid;
			if (mul == x) return mid;
			if (mul < x) l = mid + 1;
			else r = mid - 1;
		}
		long long mul = l * l;
		return mul > x? l - 1: l;
	}
};

Python

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        l, r = 0, x >> 1
        while l <= r:
            mid = (l + r) >> 1
            mul = mid ** 2
            if mul == x: return mid
            if mul < x:
                l = mid + 1
            else:
                r = mid - 1
        return l - 1 if l ** 2 > x else l

方法二：牛顿迭代法

可参考： https://en.wikipedia.org/wiki/Integer_square_root

C++

class Solution {
public:
	int mySqrt(int x) {
		long long ans = x;
		while (ans * ans > x)
			ans = (ans + x / ans) >> 1;
		return ans;
	}
};

Python

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        ans = x
        while ans * ans > x:
            ans = (ans + x // ans) >> 1
        return ans

方法三：位运算

猜测法，当前的 ans (1 << i)的平方如果不大于x，那么说明当前的位数可以是1

C++

class Solution {
public:
    int mySqrt(int x) {
        long long ans = 0;
        for(int i = 15; i >= 0; --i){ // i = 15就可以，因为x最大为2^31 - 1
            long long t = ans  (1 << i);
            if(t * t <= x)
                ans = t;
        }
        return ans;
    }
};

Python

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        ans = 0
        for i in range(15, -1, -1):
            t = 1 << i
            if (ans  t) ** 2 <= x:
                ans = t
        return ans

74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted from left to right.

The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:
1
2
3
4
5
6
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
Given target = 3, return true.

题目地址：leetcode Search a 2D Matrix

题目大意: 给定一个矩阵，这个矩阵中，每一行的元素均从小到大排好序，且每一行第一个元素大于上一行最后一个元素。给定一个数target，判断target是否存在。

思路：

两次二分。一开始先确定行，取每行最后一个数进行查找。之后在这一行进行查找该元素。
直接把矩阵看成一维的，即L=0,R=m*n-1，而每次matrix[mid/n][mid%n]即可。

C++方法一

class Solution {
	int search_row(const vector<vector<int>>& matrix, const int target) {
		int l = 0, r = matrix.size();
		while (l < r) {
			int mid = l + ((r - l) >> 1);
			if (matrix[mid][0] <= target)
				l = mid + 1;
			else
				r = mid;
		}
		return l;
	}

public:
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		if (matrix.empty() || matrix[0].empty() || matrix[0][0] > target) return false;
		int row = search_row(matrix, target) - 1;
		int l = 0, r = matrix[0].size() - 1;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			if (matrix[row][mid] == target)
				return true;
			else if (matrix[row][mid] < target)
				l = mid + 1;
			else
				r = mid - 1;
		}
		return false;
	}
};

C++方法二

class Solution {
public:
	bool searchMatrix(vector<vector<int>> &matrix, int target) {
		if (matrix.empty()) return false;
		int m = matrix.size(), n = matrix[0].size(), L = 0, R = m*n - 1;
		while (L <= R) {
			int mid = (L + R) >> 1;
			if (matrix[mid / n][mid % n] == target)
				return true;
			else if (matrix[mid / n][mid % n] < target)
				L = mid + 1;
			else
				R = mid - 1;
		}
		return false;
	}
};

python方法二

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix: return False
        m, n, = len(matrix), len(matrix[0])
        L, R = 0, m * n - 1
        while L <= R:
            mid = (L + R) >> 1
            if matrix[mid / n][mid % n] == target:
                return True
            elif matrix[mid / n][mid % n] < target:
                L = mid + 1
            else:
                R = mid - 1
        return False

81. Search in Rotated Sorted Array II

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

题目地址：leetcode Search in Rotated Sorted Array II

题目大意: 把33题的数组改为元素可以重复出现，给定一个target，判断其是否存在。

思路：

和33题相比不同的是，这题元素是可重复的，可重复对于我们的有序判断产生了影响。

原来我们直接A[L] <= A[R]说明 [L,R]为升序，现在不行了，比如11131.

现在还是进行二分搜索。

若nums[mid] == target，返回true
nums[left] < nums[mid]: 左边有序，同33题处理。
- nums[left] <= target < nums[mid] : right = mid - 1
- 否则left = mid + 1
nums[left] > nums[mid]: 右边有序，同33题处理。
- nums[mid] < target <= nums[right]: left = mid + 1
- 否则right = mid - 1
否则说明nums[left] == nums[mid]
- 无法判断应该取左还是右。如11311111和11111131
- 因此left+=1
- 正因为此，最坏情况复杂度为O(n)

C++

class Solution {
public:
	bool search(vector<int>& nums, int target) {
		int left = 0, right = nums.size() - 1;
		while (left <= right) {
			int mid = (left + right) >> 1;
			if (nums[mid] == target) return true;

			if (nums[left] < nums[mid]) {
				if (nums[left] <= target && target < nums[mid])
					right = mid - 1;
				else
					left = mid + 1;
			}
			else if (nums[left] > nums[mid]) {
				if (nums[mid] < target && target <= nums[right])
					left = mid + 1;
				else
					right = mid - 1;
			}
			else
				++left;
		}
		return false;
	}
};

Python

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: bool
        """
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) >> 1
            if nums[mid] == target: return True

            if nums[left] < nums[mid]:  # 左边有序，同33题处理。
                if nums[left] <= target < nums[mid]:
                    right = mid - 1
                else:
                    left = mid + 1
            elif nums[left] > nums[mid]:  # 右边有序，同33题处理
                if nums[mid] < target <= nums[right]:
                    left = mid + 1
                else:
                    right = mid - 1
            else:
                left += 1

        return False

153. Find Minimum in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

You may assume no duplicate exists in the array.

传送门

题意：给定一个排好序，但是经过旋转的数组（数组中无重复元素），求该数组的最小值。

思路：类似前面的81题（排好序的旋转的数组中进行二分查找），这题也一样，A[L]<=A[R]说明数组有序，直接返回A[L]

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        return self.search(num,0,len(num)-1)

    def search(self,num,L,R):
        if num[L] <= num[R]: #[L,R] are ordered
            return num[L]
        mid = (L+R)>>1
        return min(self.search(num,L,mid),self.search(num,mid+1,R))

方法2，二分搜索

设mid = (left + right) / 2

如果

nums[mid] < nums[right]：说明右半部分不可能有最小的元素，因此right = mid
nums[mid] > nums[right]：说明旋转的元素（最小值）一定在(mid, righth]之间，因此left = mid + 1

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[right]:
                left = mid + 1
            else: # nums[mid] < nums[right]
                right = mid
        return nums[left]

154. Find Minimum in Rotated Sorted Array II

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

传送门

题意：给定一个排好序，但是经过旋转的数组（数组中有重复元素），求该数组的最小值。

思路：和上面一题不同在于这题有重复元素，仅有A[L]<A[R]时，返回A[L]。

class Solution:
    # @param num, a list of integer
    # @return an integer
    def findMin(self, num):
        return self.search(num,0,len(num)-1)

    def search(self,num,L,R):
        if L == R: return num[L]
        if num[L] < num[R]: #[L,R] are ordered
            return num[L]
        mid = (L+R)>>1
        return min(self.search(num,L,mid),self.search(num,mid+1,R))

方法2：二分搜索

设mid = (left + right) / 2，如果

nums[mid] < nums[right]：说明右半部分不可能有最小的元素，因此right = mid
nums[mid] > nums[right]：说明旋转的元素（最小值）一定在(mid, righth]之间，因此left = mid + 1
nums[mid] == nums[right]：无法确定最小值的范围，但是两个元素相等，可以让right - 1来缩小范围

class Solution:
    def findMin(self, nums: List[int]) -> int:
        left = 0
        right = len(nums) - 1
        while left < right:
            mid = (left + right) >> 1
            if nums[mid] > nums[right]:
                left = mid + 1
            elif nums[mid] < nums[right]:
                right = mid
            else:
                right -= 1
        return nums[left]

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.

Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:
1
2
3
4
5
6
7
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.

Given target = 20, return false.

题目地址：leetcode Search a 2D Matrix II

题目大意 : 给定一个矩阵，该矩阵满足：每一行和每一列均为升序。给定一个数target，让你判断这个数是否在矩阵中。

思路：

直接想到的是二分搜索，对每一行进行一次二分，复杂度为O(mlogn)

C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(vector<int> &row: matrix){
            int l = 0, r = row.size() - 1;
            while(l <= r){
                int mid = l + ((r - l) >> 1);
                if(row[mid] == target) return true;
                else if(row[mid] < target) l = mid + 1;
                else r = mid - 1;
            }
        }
        return false;
    }
};

Java

public class Solution {
    boolean binary_search(int[] a, int target) {
		int L = 0, R = a.length - 1;
		while (L <= R) {
			int mid = (L + R) >> 1;
			if (a[mid] == target) return true;
			else if (a[mid] < target) L = mid + 1;
			else R = mid - 1;
		}
		return false;
	} 
	
    public boolean searchMatrix(int[][] matrix, int target) {
        for(int i=0;i<matrix.length;i++){
            if (binary_search(matrix[i], target)) return true;
	}
	return false;
    }
}

Python

class Solution(object):
    def binary_search(self, a, target):
        L, R = 0, len(a) - 1
        while L <= R:
            mid = (L + R) >> 1
            if a[mid] == target:
                return True
            elif a[mid] < target:
                L = mid + 1
            else:
                R = mid - 1
        return False

    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        for row in matrix:
            if self.binary_search(row,target):
                return True
        return False

第二种思路是设定初始点为最左下角或者最右上角。以最左下角为例，
- 当matrix[i][j] == target: 返回true不解释
- 当matrix[i][j] < target: 说明我们应该向右查找（行为升序）
- 当matrix[i][j] > target:：说明我们应该向上查找（列为降序）
- 这样复杂度为O(m+n)

C++

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        int i = matrix.size() - 1, j = 0, n = matrix[0].size();
        while(i >= 0 && j < n){
            if(matrix[i][j] == target) return true;
            else if(matrix[i][j] < target) ++j;
            else --i;
        }
        return false;
    }
};

Java

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0) return false;
		int m = matrix.length, n = matrix[0].length;
		int i = m - 1, j = 0;
		while (i >= 0 && j < n) {
			if (matrix[i][j] == target) return true;
			else if (matrix[i][j] < target) j++;
			else i--;
		}
		return false;
    }
}

Python

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix: return False
        m, n = len(matrix), len(matrix[0])
        i, j = m - 1, 0
        while i >= 0 and j < n:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                i -= 1
            else:  # matrix[i][j] < target
                j += 1
        return False

初始点为右上角的Python代码。。

class Solution(object):
    def searchMatrix(self, matrix, target):
        """
        :type matrix: List[List[int]]
        :type target: int
        :rtype: bool
        """
        if not matrix: return False
        m, n = len(matrix), len(matrix[0])
        i, j = 0, n-1
        while i < m and j>=0:
            if matrix[i][j] == target:
                return True
            elif matrix[i][j] > target:
                j -= 1
            else:  # matrix[i][j] < target
                i += 1
        return False

这是leetcode 二分搜索的题解

更多题解可以查看：https://www.hrwhisper.me/leetcode-algorithm-solution/