寻找旋转排序数组中的最小值II

假设有重复元素。

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

 

寻找旋转排序数组中的最小值

假设一个旋转排序的数组其起始位置是未知的（比如0 1 2 4 5 6 7 可能变成是4 5 6 7 0 1 2）。你需要找到其中最小的元素。你可以假设数组中不存在重复的元素。

（一）直接遍历查找（笨方法）

public int findMin(int[] nums) {    if(nums[0] < nums[nums.length - 1]){        return nums[0];    }    for(int i=0; i
     
       nums[i+1]){            return nums[i+1];        }    }    return -1;}
     

（二）二分法

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

 

 

x的n次幂

实现 pow(double x, int n)

（一）直接相乘n次

public double myPow(double x, int n) {    if(x == 0){        return 0;    }    if(n == 0){        return 1.0;    }    if(n < 0){        return 1.0 / myPow(x, -n);    }    double res = x;    while(n > 1){        res *= x;        n--;    }    return res;}

（二）用二分法来加速计算x^n=x^(n/2)* x^(n/2)，即x^10=x^5*x^5，递归运算。这种计算N次幂只要相乘O(logN)次。

public double myPow(double x, int n){    if(x == 0){        return 0;    }    if(n == 0){        return 1.0;    }    if(n < 0){        return 1.0 / myPow(x, -n);    }        double res = myPow(x, n/2);    if(n%2 == 1){        res = res * res * x;    }else{        res = res * res;    }    return res;}

（三）

递归毕竟比较浪费时间，且会有很多重复计算。因此最好能换成非递归的方式来实现二分法。

考虑x^23，可以先从x ->x^2 -> x^4 -> x^8 -> x^16 取result1 = x^16，然后23-16=7。我们只要计算x^7再与result1相乘就可以得到x^23。

对于x^7也可以采用这种方法。取result2 = x^4，然后7-4=3，只要计算x^3再与result2相乘就可以得到x^7。由此可以将x^23写成x^16 * x^4* x^2 * x，即23=16+4+2+1，而23 = 10111(二进制)，所以只要将n化为二进制并由低位到高位依次判断如果第i位为1，则result *=x^(2^i)。

public double myPow(double x, int n){    if(x == 0){        return 0;    }    if(n == 0){        return 1.0;    }    if(n < 0){        return 1.0 / myPow(x, -n);    }        double res = 1.0;    while(n > 0){        if((n & 1) != 0){            res *= x;        }        x *= x;        n >>= 1;    }    return res;}

进一步的优化，如像48=110000(二进制)这种低位有很多0的数，可以先过滤掉低位的0再进行计算，这样也会提高一些效率。

public double myPow(double x, int n){    if(x == 0){        return 0;    }    if(n == 0){        return 1.0;    }    if(n < 0){        return 1.0 / myPow(x, -n);    }        while((n & 1) == 0){        n >>= 1;        x *= x;    }        double res = 1.0;    while(n > 0){        if((n & 1) != 0){            res *= x;        }        x *= x;        n >>= 1;    }    return res;}

 

 

寻找峰值

在一个数组A中：相邻位置的数字不同；A[0] < A[1] 并且 A[n - 2] > A[n - 1]

找出数组中的一个峰值，即A[P] > A[P-1]且A[P] > A[P+1]。

思路：遍历当然可以。另外一种方式就是利用二分查找。

首先我们的目标是找到中间节点mid， 1.如果大于两边的数字那么就是找到了答案，直接返回找到的答案。 2. 如果左边的节点比mid大，那么我们可以继续在左半区间查找，因为左边可以证明一定存在一个peak element， 为什么呢？因为题目告诉了我们区间[0, mid - 1] 中num[0] < num[1]，我们刚才又知道num[mid - 1]>num[mid]了，所以[0, mid - 1] 之间肯定有一个peak element。 3. 如果num[mid - 2] > num[mid - 1]，那么我们就继续在[0, mid - 2]区间查找，那么同理可以在右边的区间找到一个peak element。所以继续这个二分搜索的方式最后我们就能找到一个peak element。

public int findPeak(int[] A) {    int start = 1;    int end = A.length - 2;    while(start+1

 

 

搜索旋转排序数组

有一个排序的按未知的旋转轴旋转的数组(比如，0 1 2 4 5 6 7 可能成为4 5 6 7 0 1 2)。给定一个目标值进行搜索，如果在数组中找到目标值返回数组中的索引位置，否则返回-1。

      (加入有重复元素，怎么做？lintcode上)

public int search(int[] A, int target) {    if (A == null || A.length == 0) {        return -1;    }    int start = 0;    int end = A.length - 1;    int mid;        while (start < end) {        mid = (end + start) / 2;        if (A[mid] == target) {            return mid;        }                if (A[start] < A[mid]) { // mid左边有序            if (A[start] <= target && target < A[mid]) {                end = mid - 1;            } else {                start = mid + 1;            }        } else { // mid右边有序            if (target <= A[end] && target > A[mid]) {                start = mid + 1;            } else {                end = mid -1;            }        }    }        if (A[start] == target) {        return start;    }    if (A[end] == target) {        return end;    }    return -1;}

 

x的平方根

实现 int sqrt(int x) 函数，计算并返回 x 的平方根。举例：sqrt(4) = 2，sqrt(5) = 2。

public static int sqrt(int x) {    int low = 0, high = x;        while(low <= high) {        int mid = (high + low)/2;        long square = (long)mid * (long)mid;        long square1 = (long)(mid + 1) * (long)(mid + 1);        long square2 = (long)(mid - 1) * (long)(mid - 1);        if(square == x)             return mid;        if(square < x && square1 > x)             return mid;        if(square > x && square2 < x)            return mid - 1;                if(square < x)             low = mid + 1;        else             high = mid - 1;    }    return -1;}

 

 

搜索插入位置

给定一个排序数组和一个目标值，如果在数组中找到目标值则返回索引。如果没有，返回到它将会被按顺序插入的位置。（假设在数组中无重复元素）

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

 

 

二维矩阵中的二分查找

二维矩阵中，每一行每一列都递增。查找目标target是否存在。

思路：从矩阵的左下角开始查找。

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

 

 

 

二分查找

1、二分查找的递归实现

public int bsearch(int[] arr, int low, int high, int target){    if(low > high)    return -1;    int mid = (low+high)/2;    if(arr[mid] > target){        return bsearch(arr, low, mid-1, target);    }    if(arr[mid] < target){        return bsearch(arr, mid+1, high, target);    }    return mid;}

2、非递归

public int bsearchWithoutRec(int[] arr, int low, int high, int target){    while(low<=high){        int mid = (low+high)/2;        if(arr[mid] > target)            high = mid-1;        else if(arr[mid] < target)            low = mid+1;        else            return mid;    }    return -1;}

 

 

 

3、二分法寻找严格上界（大于target的第一个数）

public int bsearchUpper(int[] arr, int low, int high, int target){    if(low>high || target>=arr[high])        return -1;        int mid = (low + high)/2;    while(high>low){        if(arr[mid]>target){ // 大于            //如果当前找到的数大于目标数时，它可能就是我们要找的数，            //所以需要保留这个索引，也因此high=mid, 而没有减1。            high = mid;         }else{
   // 不大于            low = mid + 1;        }            mid = (low+high)/2;    }    return mid;}

4、二分法寻找严格下界（小于target的第一个数）

public int bsearchLower(int[] arr, int low, int high, int target){    if(high

5、二分法寻找上界（大于等于target的第一个数）

public int bsearchUpperEqual(int[] arr, int low, int high, int target){    if(low>high || target>arr[high]) // 去掉等号        return -1;        int mid = (low + high)/2;    while(high>low){        if(arr[mid]>=target){ // 大于等于            high = mid;         }else{            low = mid + 1;        }            mid = (low+high)/2;    }    return mid;}

6、二分法寻找下界（小于等于target的第一个数）

public int bsearchLowerEqual(int[] arr, int low, int high, int target){    if(high

 

7、二分法查找旋转数组

// {7, 11, 13, 17, 2, 3, 5}public int bsearchRotatedArray(int[] arr, int low, int high, int target){    while(low<=high){        int mid = (high+low)/2;        if(target
     
      arr[mid]){            if(arr[low]
     

 8、给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

public int binarySearch(int[] nums, int target) {    if(nums==null || nums.length==0){        return -1;    }        int start = 0;    int end = nums.length-1;        while(start+1
     
      nums[mid]){            start = mid;        }else{            end = mid;        }    }        if(nums[start] == target){        return start;    }    if(nums[end] == target){        return end;    }    return -1;}
     

 10、搜索排序数组中的目标数。

给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。如果目标值不在数组中，则返回[-1, -1]

分析：分布找出左边界和右边界。

public int[] searchRange(int[] A, int target) {    if (A.length == 0) {        return new int[]{-1, -1};    }        int start, end, mid;    int[] bound = new int[2];         // search for left bound    start = 0;     end = A.length - 1;    while (start + 1 < end) {        mid = start + (end - start) / 2;        if (A[mid] == target) {            end = mid;        } else if (A[mid] < target) {            start = mid;        } else {            end = mid;        }    }    if (A[start] == target) {        bound[0] = start;    } else if (A[end] == target) {        bound[0] = end;    } else {        bound[0] = bound[1] = -1;        return bound;    }        // search for right bound    start = 0;    end = A.length - 1;    while (start + 1 < end) {        mid = start + (end - start) / 2;        if (A[mid] == target) {            start = mid;        } else if (A[mid] < target) {            start = mid;        } else {            end = mid;        }    }    if (A[end] == target) {        bound[1] = end;    } else if (A[start] == target) {        bound[1] = start;    } else {        bound[0] = bound[1] = -1;        return bound;    }        return bound;}