Leetcode练习1.二分查找

思路：这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件，当看到题目描述满足如上条件的时候，可以想一想是不是可以用二分法了。

定义left、right指针，比较目标元素和中间元素的大小，然后不断缩小左右指针的范围继续寻找目标元素。
实际使用求中间mid索引建议用这种方法：int mid = left + (right-left)/2; 可以防止left+right溢出（超出整数范围）。

复杂度：时间复杂度O(logn)，空间复杂度O(1)

class Solution {
    public int search(int[] nums, int target) {
        int low = 0 ;
        int high = nums.length-1;
        while (high>=low){
            int mid=low+(high-low)/2;//注意尽量不要用(low+high)/2,避免溢出
            int num=nums[mid];
            if(num==target){
                return mid;
            }else if(num>target){
                high=mid-1;
            }else{
                low=mid+1;
            }
        }
        return -1;
    }
}

思路：注意到一个性质：当一个版本为正确版本，则该版本之前的所有版本均为正确版本；当一个版本为错误版本，则该版本之后的所有版本均为错误版本。我们可以利用这个性质进行二分查找。
将左右边界分别初始化为 1 和 n，其中 n 是给定的版本数量。设定左右边界之后，每次我们都依据左右边界找到其中间的版本，检查其是否为正确版本。如果该版本为正确版本，那么第一个错误的版本必然位于该版本的右侧，我们缩紧左边界；否则第一个错误的版本必然位于该版本及该版本的左侧，我们缩紧右边界。

public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left=1,right=n,mid=1;
        while(left					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5611065.html