33/81. Search in Rotated Sorted ArrayI/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.
复杂度: time O(logn) space O(1)
思路: 因为rotate的缘故,当我们切取一半的时候可能会出现mid在左半边区间,或者右半边区间的情况,所以我们要做进一步的判断。假设数组是A,起始start,终止end,还有中间位置是mid。在每次迭代中,分三种情况:

A[mid] = target 找到target
A[mid] > A[start] 说明mid在左半边区间(4 5 6 7)有序的, 那么就要判断target是否在start与mid之间, 如果在的话则把m设为end边界, 否则的话target就在另外的一半, 把mid设为start边界
如果A[mid] < A[start], 说明mid在右半边区间(0 1 2 ), 那么就判断target是不是在mid到end之间.如果target在的话把mid设为start, 否则把mid设为end
最后再判断A[start],A[end]与target的关系.

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > nums[start]) { // 4 5 6 7
                if (nums[mid] >= target && target >= nums[start]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else { // 0 1 2
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        if (nums[start] == target) {
            return start;
        } else if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

包含duplicate的:
复杂度: time O(n), space O(1),
思路: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[mid] > nums[start]) { // 4 5 6 7
                if (target >= nums[start] && nums[mid] >= target) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else if (nums[mid] < nums[start]) { // 0 1 2
                if (target <= nums[end] && nums[mid] <= target) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else {
                start++;
            }
        }
        if (nums[start] == target || nums[end] == target) 
            return true;
        return false;
    }
}
Advertisements

153/154. Find Minimum 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).

Find the minimum element.

You may assume no duplicate exists in the array.
思路: 153中不包括duplicate. 直接二分,target选最右边元素。 每次mid跟target进行比较,如果大于target,说明mid在左边逆序,最小值在右边,start=mid; 如果小于target,说明mid在右边,往左边找,end = mid; 最后再返回start跟end中较小的元素。

复杂度: time O(logn), space O(1)

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;
        int target = nums[end];
        while(start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] &gt;= target) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (nums[start] &lt;= nums[end]) {
            return nums[start];
        }
        return nums[end];
    }
}

154 存在duplicates的情况。
思路: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;
复杂度: time O(n), space O(1)

public class Solution {
    public int findMin(int[] nums) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;
        while(start + 1 &lt; end) {
            int mid = start + (end - start) / 2;
            if (nums[end] &lt; nums[mid]) {
                start = mid;
            } else if (nums[end] &gt; nums[mid]) {
                end = mid;
            } else { 
                end--;
            }
        }
        return Math.min(nums[start], nums[end]);

    }
}

74/240. Search a 2D Matrix I/II

  1. 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.

思路: 给定的matrix中,下一行的头元素总是大于上一行的尾元素,整个二维数组中的元素是单调递增,一如何定位某一点的坐标, start=0, end= row*col-1; 某一点的表示matrix[index/col][index%col]。
复杂度: time: O(log(MN)) space: O(1)

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

    }
}

Search a 2D Matrix II
[
[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]
]
思路: 从左下角开始 matrix[row – 1][0],往右上角搜索, 如果当前点大于target就往上走,小于target就往右走.
复杂度: time: O(m + n) space O(1)

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

Binary Search(二分搜索)总结

数值相关的二分

67.Sqrt(x): 1 -> x的区间来二分.start=1,end=x; 最后边界条件先检查startstart<=x, 然后看endend0 return pow(x,n) 否则return 1/pow(x,Math.abs(n)); pow实现思路就是二分,if(n==0) return1;if(n==1) return x; half = pow(x,n/2);return (n % 2 == 0) ? halfhalf :halfhalf*x,
34,Search for a Range(搜索范围)/搜索duplicates: 可以两次二分查找分别找到给定target的起始点跟终止点. 注意每次二分搜索后start跟end的边界条件检查

一维数组跟二维数组里的二分搜索

  1. Search Insert Position: 给定数组是有序的,
    target array[length – 1] return length;
    array[0]nums[mid+1]) => true, if(nums[mid] <nums[mid-1]) end = mid;说明mid左边是单调递减的,应该往左边找。否则往右边找.

74.Search a 2D Matrix I: 给定的matrix中,下一行的头元素总是大于上一行的尾元素,整个二维数组中的元素是单调递增,一如何定位某一点的坐标, start=0, end= row*col-1; 某一点的表示matrix[index/col]
240.Search a 2D Matrix II: 从左下角开始 matrix[row – 1][0],往右上角搜索,如果当前点大于target就往上走,小于target就往右走

Rotated Sorted Array

153.Find Minimum in Rotated Sorted Array I: 153中不包括duplicate. 直接二分,target选最右边元素。 每次mid跟target进行比较,如果大于target,说明mid在左边逆序,最小值在右边,start=mid; 如果小于target,说明mid在右边,往左边找,end = mid; 最后再返回start跟end中较小的元素
154.Find Minimum in Rotated Sorted Array II: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;
33. Search in Rotated Sorted ArrayI:
因为rotate的缘故,当我们切取一半的时候可能会出现mid在左半边区间,或者右半边区间的情况,所以我们要做进一步的判断。假设数组是A,起始start,终止end,还有中间位置是mid。在每次迭代中,分三种情况:
A[mid] = target 找到target
A[mid] > A[start] 说明mid在左半边区间(4 5 6 7)有序的, 那么就要判断target是否在start与mid之间, 如果在的话则把m设为end边界, 否则的话target就在另外的一半, 把mid设为start边界
如果A[mid] < A[start], 说明mid在右半边区间(0 1 2 ), 那么就判断target是不是在mid到end之间.如果target在的话把mid设为start, 否则把mid设为end
最后再判断A[start],A[end]与target的关系
81. Search in Rotated Sorted ArrayII: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;

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

思路: 由于给定的一维数组是有序的,先判断头元素跟尾元素跟target的大小,
target array[length -1],返回length. 都不满足则二分查找

public class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;

        if (nums[0] > target) return 0;
        else if (nums[nums.length - 1] < target) return nums.length; 
        else {
            int start = 0;
            int end = nums.length - 1;
            int index = -1;
            while(start + 1 < end) {
                int mid = start + (end - start) / 2;
                if (nums[mid] == target) {
                    return mid;
                } else if(nums[mid] > target) {
                    end = mid;
                } else {
                    start = mid;
                }
            }

            if (nums[start] < target && nums[end] >= target) {
                return end;
            }
            return start;

        }
    }
}

367. Valid Perfect Square

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

思路: 二分.注意二分的时候用long类型, 最后转换为int.

public class Solution {
    public boolean isPerfectSquare(int num) {
        if (num &lt; 0) return false;
        if (num == 1) return true;
        long start = 0;
        long end = num;
        while(start + 1 &lt; end) {
            long mid = start + (end - start) / 2;
            if (mid * mid == num) {
                return true;
            } else if (mid * mid &gt; num) {
                end = mid;
            } else {
                start = mid;
            }
        }

        if ((int)(start * start) == num || (int)(end * end) == num) {
            return true;
        } 
        return false;
    }
}