二分法

二分搜索算法

• 用于在有序集合中查找元素，时间复杂度为ologN
• 二分具有二段性：给定条件可以将集合中元素分为两部分，一部分满足条件，一部分不满足条件 ---- # 步骤
• 首先将（有序）集合分成两段，左边段[left,n-1]右边段[n,right]
• 若mid落在左半段（<n）left=mid
• 若mid落在右半段（>=n）right=mid
• 然后else中left向右移动（加1），right向左移动（减1）
• 若出现left=mid,计算mid要向上取整（加1）
• 勤加练习，必能掌握 ### java实现

  int arr[]=new int[]{1,2,3,4,5,6};
  int left=0,right=5;
  int left1=0,right1=5;
  int k=3;//要查找的值
  while(left<right) {//查找上界
  	int mid=(left+right)>>1;
  	if(arr[mid]>=k) {//界限可变
  			right=mid;
  		}
  	else {
  			left=mid+1;
  		}
  	}
  	while(left1<right1) {//查找下界
  		int mid=(left1+right1+1)>>1;
  		if(arr[mid]<k) {
  			left1=mid;
  		}
  		else {
  			right1=mid-1;
  		}
  	}
  	System.out.println(left+" "+left1);