leet binary search

leetcode

1. Search Insert Position My Submissions Question
   Total Accepted: 91279 Total Submissions: 249084 Difficulty: Medium
   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

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

2

Search a 2D Matrix
15:00
Start
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.
Have you met this question in a real interview? Yes
Example
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3, return true.
Challenge
O(log(n) + log(m)) time

public boolean searchMatrix(int[][] matrix, int target) {
    int row_num = matrix.length;
    int col_num = matrix[0].length;
    int begin = 0, end = row_num * col_num - 1;
    while(begin <= end){
        int mid = (begin + end) / 2;
        int mid_value = matrix[mid/col_num][mid%col_num];
        if( mid_value == target){
            return true;
        }else if(mid_value < target){
    //Should move a bit further, otherwise dead loop.
            begin = mid+1;
        }else{
            end = mid-1;
        }
    }
    return false;
}