算法|二分

704. 二分查找

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right){
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else return mid;
        }
        return -1;
    }
}

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else return mid;
        }
        return -1;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
    private int searchRange(int[] nums, int target, boolean isLeft) {
        int left = 0;
        int right = nums.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                //相等
                if (isLeft) {
                    if (mid == 0 || nums[mid - 1] != target) {
                        return mid;
                    } else {
                        right = mid - 1;
                    }
                } else {
                    if (mid == nums.length - 1 || nums[mid + 1] != target) {
                        return mid;
                    } else {
                        left = mid + 1;
                    }
                }

            }
        }
        return result;
    }
    public int[] searchRange(int[] nums, int target) {
        if  (nums.length == 0) return new int[] {-1, -1};
        int leftIndex = searchRange(nums, target, true);
        if (leftIndex == -1) return new int[] {-1, -1};
        int rightIndex = searchRange(nums, target, false);
        return new int[] {leftIndex, rightIndex};
    }
}

69. x 的平方根

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        if (x == 1) return 1;
        int left = 1;
        int right = x / 2;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int val = x / mid;
            if (val > mid) {
                left = mid + 1;
            } else if (val < mid) {
                 right = mid - 1;
            } else return mid;
        }
        return right; 
    }
}

611. 有效三角形的个数

class Solution {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int result = 0;
        for (int i = 0; i < n; i++){
            for (int j = i + 1; j < n; j++){
                int target = nums[i] + nums[j];
                int left = j + 1;
                int right = n - 1;
                int k = j;
                while (left <= right){
                    int mid = left + (right - left) / 2;
                    if (nums[mid] < target) {
                        //符合条件的
                        left = mid + 1;
                        k = mid;
                    } else {
                        right = mid - 1;
                    }
                }
                result += (k - j);
            }
        }
        return result;
    }
}

189. 轮转数组

class Solution {
    private void rever(int[] nums, int left, int right) {
        while (left < right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k = k % n;
        rever(nums, 0, n - 1);
        rever(nums, 0, k - 1);
        rever(nums, k, nums.length - 1);
    }
}

4. 寻找两个正序数组的中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int length = m + n;
        int i = 0;
        int j = 0;
        int left = 0;
        int rigth = 0;
        for (int k = 0; k <= length / 2; k++){
            left = rigth;
            if (i < m && j < n) {
                if (nums1[i] < nums2[j]) {
                    rigth = nums1[i++];
                } else {
                    rigth = nums2[j++];
                }
            } else if (i >= m) {
                rigth = nums2[j++];
            } else {
                rigth = nums1[i++];
            }
        }
        if (length % 2 == 0) {
            return (left + rigth) / 2.0;
        } else {
            return rigth;
        }
    }
}

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }
        int m = nums1.length;
        int n = nums2.length;
        int length = m + n;
        int left = 0;
        int rigth = m;
        int res1 = 0;
        int res2 = 0;
        while (left <= rigth){
            int mid1 = left + (rigth - left) / 2;
            int mid2 = (length + 1) / 2 - mid1;
            int l1 = mid1 == 0 ? Integer.MIN_VALUE : nums1[mid1 - 1];
            int l2 = mid2 == 0 ? Integer.MIN_VALUE : nums2[mid2 - 1];
            int r1 = mid1 == m ? Integer.MAX_VALUE : nums1[mid1];
            int r2 = mid2 == n ? Integer.MAX_VALUE : nums2[mid2];
            if (l1 > r2) {
                rigth = mid1 - 1;  
            }  else if (l2 > r1) {
                left = mid1 + 1;
            } else {
               res1 = Math.max(l1, l2);
               res2 = Math.min(r1, r2);
               break;
            }
        }
        if (length % 2 == 0) return (res1 + res2) / 2.0;
        else return res1;
    }
}

33. 搜索旋转排序数组

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int rigth = nums.length - 1;
        while (left <= rigth){
            int mid = left + (rigth - left) / 2;
            if (target == nums[mid]){
                return mid;
            } else if (nums[rigth] > nums[mid]) {
                //右边有序
                if (nums[mid] < target && target <= nums[rigth]) {
                    left = mid + 1;
                } else {
                    rigth = mid - 1;
                }
            } else {
                //左边有序
                if (nums[left] <= target && target < nums[mid]) {
                    rigth = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}

81. 搜索旋转排序数组 II

class Solution {
    public boolean search(int[] nums, int target) {
        int left = 0;
        int rigth = nums.length - 1;
        while (left <= rigth){
            int mid = left + (rigth - left) / 2;
            if (nums[mid] == target) return true;
            else if (nums[mid] == nums[rigth]) {
                rigth--;
            } else if (nums[mid] == nums[left]) {
                left++;
            } else if (nums[mid] < nums[rigth]) {
                if (nums[mid] < target && target <= nums[rigth]) {
                    left = mid + 1;
                } else {
                    rigth = mid - 1;
                }
            } else {
                if (nums[mid] > target && target >= nums[left]) {
                    rigth = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return false;
    }
}

面试题 10.03. 搜索旋转数组

class Solution {
    public int search(int[] nums, int target) {
        if (target == nums[0]) return 0;
        int left = 0;
        int rigth = nums.length - 1;
        while (left <= rigth) {
            int mid = left + (rigth - left) / 2;
            if (nums[mid] == target) {
                if (mid == 0 || target != nums[mid - 1]) return mid;
                rigth = mid - 1;
            } else if (nums[mid] == nums[left]) {
                left++;
            } else if (nums[mid] == nums[rigth]) {
                rigth--;
            } else if (nums[mid] < nums[rigth]) {
                if (nums[mid] < target && target <= nums[rigth]) {
                    left = mid + 1;
                } else {
                    rigth = mid - 1;
                }
            } else {
                if (nums[mid] > target && target >= nums[left]) {
                    rigth = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
}

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

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

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

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