【数据结构】二分查找（复杂度及练习）5.13

基础版回顾

package 二分查找;
 
public class BinarySearch {
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
	}
     public static int binarySearchBasic(int[] a,int target) {
    	 int i=0,j=a.length-1; //设置指针初值
    	 while(i<=j) { //范围有内容
    		 int m=(i+j)/2;
    		 if(target<a[m]) {
    			 j=m-1;
    		 }else if(target>a[m]) {
    			 i=m+1;
    		 }else {
    			 return m;
    		 }
    	 }
    	 return -1;
	}
 
}

改动版：

j的边界

注意:j不会指向目标值，要改变i＜＝j

package 二分查找;

public class BinarySearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
	}
     public static int binarySearchBasic(int[] a,int target) {
    	 int i=0,j=a.length; //设置指针初值
    	 while(i<j) { //范围有内容
    		 int m=(i+j)>>>2;
    		 if(target<a[m]) {
    			 j=m;
    		 }else if(target>a[m]) {
    			 i=m+1;
    		 }else {
    			 return m;
    		 }
    	 }
    	 return -1;
	}

}

如何衡量算法的好坏？

1.最差的执行情况

2.假设每行执行语句时间相同

1）时间复杂度；一个算法的执行，随数据规模增大，而增长的时间成本（不依赖于环境因素）

大O表示法：

1）空间复杂度：一个算法执行数据规模增大，而增长的额外空间成本。

练习:

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

为什么用i+（j-i）/2求中间值？

在二分查找中，计算 mid（中间值）的标准方法是：

int mid = (i + j) / 2;

但这种方法在 i 和 j 很大时可能溢出（例如，i = 2^30, j = 2^30 + 100，i + j 会超出 int范围）。  

改进方法：防止溢出

为了避免 (i + j) 溢出，我们可以用数学等价变形：

mid = (i + j) / 2  

     = i/2 + j/2  

     = i + (j - i)/2

所以，更安全的写法是：

int mid = i + (j - i) / 2;

说明：

不会溢出，因为 j - i最多是 x（初始 j = x）。