Search for a Range

Given a sorted array of integers, 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].

就是两次二分找两次边界

public class Solution {
    //Time: O(logn)  Space: O(1)
    public int[] searchRange(int[] A, int target) {
        int[] res = new int[2];
        res[0] = res[1] = -1;
        if (A == null || A.length == 0) {
            return res;
        }
        
        int left = 0;
        int right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (target <= A[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (A[left] == target) {
            res[0] = left;
        } else if (A[right] == target) {
            res[0] = right;
        }
        
        left = 0;
        right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (target < A[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (A[right] == target) {
            res[1] = right;
        } else if (A[left] == target) {
            res[1] = left;
        }
        return res;
    }
}

Search in Rotated Sorted Array I & 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).

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.

二分法，对于旋转的数组，至少有一半是已经sorted，首先判断那部分是sorted，再判断target在哪部分里。

 public class Solution {  
    //Time: O(logn) Space: O(1)  
    public int search(int[] A, int target) {  
           if (A == null || A.length == 0) {  
                return -1;  
           }  
             
           int start = 0;  
           int end = A.length - 1;  
           while (start + 1 < end) {  
                int mid = start + (end - start) / 2;  
                if (A[mid] == target) {  
                     return mid;  
                }   
                if (A[start] < A[mid]) {  
                     if (A[start] <= target && target < A[mid]) { // left are sorted  
                          end = mid;  
                     } else {  
                          start = mid;  
                     }  
                } else {  
                     if (A[mid] < target && target <= A[end]) { // right are sorted  
                          start = mid;  
                     } else {  
                          end= mid;  
                     }  
                }  
           }  
             
           if (A[start] == target) {  
                return start;  
           } else if (A[end] == target){  
                return end;  
           }  
             
           return -1;  
    }  
} 

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.

public class Solution {
    //Time: O(n) worst case.  Space: O(1)
    public boolean search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return false;
        }
        
        int left = 0;
        int right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) {
                return true;
            } else if (A[left] < A[mid]) {
                if (A[left] <= target && A[mid] > target) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else if (A[mid] < A[right]) {
                if (A[mid] < target && target <= A[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            } else {
                if (A[left] == A[mid]) {
                    left++;
                }
                if (A[right] == A[mid]) {
                    right--;
                }
            }
        }
        
        if (A[left] == target || A[right] == target) {
            return true;
        }
        return false;
    }
}

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,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
] 

Given target = 3, return true.

二分法。

public class Solution {
    //Time: O(log(m*n))  Space: O(1)
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        
        int m = matrix.length;
        int n = matrix[0].length;
        int start = 0;
        int end = m * n - 1;
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (matrix[mid / n][mid % n] == target) {
                return true;
            } else if (matrix[mid / n][mid % n] > target) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (matrix[start / n][start % n] == target || matrix[end / n][end % n] == target) {
            return true;
        }
        return false;
    }
}

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

二分搜索法

public class Solution {
    //Time: O(logn)  Space: O(n)
    public int searchInsert(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int left = 0;
        int right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) {
                return mid;
            } else if (A[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        
        if (A[left] >= target) {
            return left;
        } else if (A[right] >= target) {
            return right;
        } else {
            return right + 1;
        }
    }
}