​折半查找
​猜数字大小

活动地址：CSDN21天学习挑战赛

目录

1.折半查找

1.1 定义​

1.2 说明

1.3 代码示例

1.4 复杂度

1.5 优缺点

2.猜数字大小

2.1 说明

2.2 解法

2.3 复杂度

---

1.折半查找

1.1 定义​

折半搜索，也称二分搜索、对数搜索，是一种在有序数组中查找某一特定元素的搜索算法。

1.2 说明

搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

1.3 代码示例

1）首先确定整个查找区间的中间位置 mid = (left + right)/2 。

2）用待查关键字值与中间位置的关键字值进行比较；若相等，则查找成功；若大于，则在后（右）半个区域继续进行折半查找；若小于，则在前（左）半个区域继续进行折半查找。

3）对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。折半查找的存储结构采用一维数组存放

 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) {
                return mid;
            }else if(nums[mid] > target) {
                right = mid - 1;
            }else{
               left = mid + 1;
            }
        }
        return -1;
    }

1.4 复杂度

时间复杂度：O（log N）

空间复杂度：O（1）

1.5 优缺点

优点：

比较次数少，查找速度快，平均性能好

缺点：

待查表为有序表，且插入删除困难，

边界范围容易搞混，终止条件的确定

经常变动而查找频繁的有序列表

2.猜数字大小

2.1 说明

• 每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
• 如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
• -1：我选出的数字比你猜的数字小 pick < num
• 1：我选出的数字比你猜的数字大 pick > num
• 0：我选出的数字和你猜的数字一样。恭喜！你猜对了

2.2 解法

 记选出的数字为 pick,猜测的数字 为 num。若gess(x) <= 0 ,说明  pick <= num,否则 pick >= num

使用二分查找来求出答案pick

通过while 循环 来直到区间左右端点相同就退出循环

使用 mid = left + (right - left) / 2 而不使用  (right - left) / 2 ， 是为了防止计算时溢出

通过 guess(mid) <= 0 来知道要找的数字在 [left , mid ] 区间

否则在 [mid  + 1, right] 区间

最终 端点 left == right 时，区间缩为一个点，就是要找的数字

  public int guessNumber(int n) {
        int left = 1, right = n;
	    while (left < right) {
		   int mid = left + (right - left) /2;
		   if (guess(mid) <= 0) {
			   right = mid;
		    } else {
			    left = mid + 1;
		    }
        }
    	return left;
    }

2.3 复杂度

时间复杂度：

O(logn)。时间复杂度即为二分的次数，每次二分我们将区间的长度减小一半，直至区间长度为 1 时二分终止，而区间初始长度为 nn，因此二分次数为 O(logn)。

空间复杂度：O(1)。