Leetcode Study Day 54

Search Insert Position

Given a sorted array of distinct integers 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 must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4
 
Constraints:
1 <= nums.length <= 10^4
-10^4 <= nums[i] <= 10^4
nums contains distinct values sorted in ascending order.
-10^4 <= target <= 10^4

Binary Search Solution

We first initialise two pointers, left and right. left is the index of the first element in the array, right is the index of the last element in the array. Then we iterate through the array and update the left and right pointers. If the target is found, we return the index. If the target is not found, we return the index where it would be if it were inserted in order.

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

Search a 2D Matrix

You are given an m x n binary matrix grid. An island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Example 1:
Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
Output: true

Input: matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
Output: false

Binary Search Solution

We use binary search twice to find the answer.

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int top = 0;
        int bottom = m - 1;
        while (top <= bottom){
            int m = top+ (bottom-top)/2;
            if (matrix[m][0] < target)
                top = m + 1;
            else if (matrix[m][0] > target)
                bottom = m - 1;
            else 
                return true;
        }
        int row = bottom;
        if (row < 0) return false;
        for (int left = 0, right = n - 1; left <= right;){
            int middle = left + (right-left) / 2;
            if(matrix[row][middle] < target)
                left = middle + 1;
            else if (matrix[row][middle] > target)
                right = middle - 1;
            else 
                return true;
        }
        return false;
    }
};