算法题目

1.使用二分查找法，统计一个有序数组有多少个重复的目标值。
（1）题目可以通过二分法查找目标值最左端的位置（l)和目标值最右端的位置(r)，然后r-l+1得出共有多少位置。
（2）二分法的思想：算法的输入是一个有序的数组arr,和一个目标值target。进行二分查找要定义两个变量分别赋值头节点和尾节点（left = 0,right = arr.length-1),和一个mid变量（mid = (left+right)/2）。
算法的步骤：①赋值left = 0,right = arr.length-1②若left < right进行循环：mid = (left+right)/2,判断arr[mid] < target:left = mid+1,判断arr[mid]>=target:right = mid。进行下一个循环。需要注意的是若数组里有多个目标值该二分法可以定位到最左端的值。若要定位到最右端的值需要改进。

//java
package july16;

public class Solution {
    public int search(int[] nums, int target) {
        if (nums.length==0){
            return 0;
        }
        int right=twodivright(nums,target);
        int left=twodivleft(nums,target);
        System.out.println(right);
        System.out.println(left);
        return 0;

    }
    public int twodivright(int[] a,int target){
        int length = a.length;
        int low = 0;
        int hight = length-1;
        int mid=0;
        while (low<hight){
            if((low+hight)%2==0) {
                mid = (low+hight)/2;
            }else {
                mid = (low+hight)/2+1;
            }

            if(a[mid] > target){
                hight = mid - 1;
            }else{
                low = mid;
            }
        }
        //System.out.println(mid);
        return low;
    }
    //java进行二分查找
    public int twodivleft(int[] a,int target){
        int length = a.length;
        int low = 0;
        int hight = length - 1;
        int mid;
        while (low < hight){
            mid = (low + hight) / 2;
            if(a[mid] < target){
                low = mid + 1;
            }else {
                hight = mid;
            }
        }
        //System.out.println(hight);
        return hight;
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        int [] a = {7,7};
        int target = 8;
        s.search(a,target);
    }
}