算法——二分查找（leetcode704）

对于二分查找而言,首先我们得到的查找数组必须是一个有序数组,接着通过数组的两端得到左指针和右指针继而得到中间指针指向数组中间元素,将中间元素与目标值比较如果大于目标值舍弃数组中间元素右边的一半将右指针重置为中间指针下标-1中间指针重置为左右指针下标之和除以2（如果中间元素与目标值比较小于目标值则舍弃数组中间元素左边的一半将左指针重置为中间指针下标+1）然后就得到剩下左右指针所包括的待对比数组元素重复上述步骤直至找出目标值或者左指针下标大于右指针下标即未找到目标元素。

如下分别是左右指针数组边界左闭右闭和左闭右开两种情况的代码

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

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

原文地址：https://blog.csdn.net/Lemon_man_/article/details/143715498

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！