x的平方根
搜索旋转排序数组
假设有重复元素。
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.length-1; i++){ if(nums[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]; }
实现 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<end){ int mid = (start+end)/2; if(A[mid]<A[mid-1]){ end = mid; }else if(A[mid]<A[mid+1]){ start = mid; }else{ end = mid; } } if(A[start]<A[end]){ return end; }else{ return start; } }
搜索旋转排序数组
有一个排序的按未知的旋转轴旋转的数组(比如，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<matrix[0].length){ if(matrix[m][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<low || target<=arr[low]) return -1; int mid = (low+high+1)/2; while(low<high){ if(arr[mid]<target){ low = mid; }else{ high = mid-1; } mid = (low+high+1)/2; } return mid; }
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<low || target<arr[low]) return -1; int mid = (low+high+1)/2; while(low<high){ if(arr[mid]<=target){ low = mid; }else{ high = mid-1; } mid = (low+high+1)/2; } return mid; }
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[mid]<arr[high]){ // higher部分是递增，target在mid左侧 high = mid-1; }else{ // lower部分是递增的 if(target<arr[low]){ // target 在被旋转走的区域，调整low low = mid+1; }else{ high = mid-1; } } }else if(target>arr[mid]){ if(arr[low]<arr[mid]){// lower部分是递增的 low = mid+1; }else{ // higher部分是递增 if(arr[high]<target){ high = mid-1; }else{ low = mid+1; } } }else{ return mid; } } return -1; }
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<end){ int mid = (end+start)/2; if(target>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; }