二分讲解

二分概述

12.2.1 基本定义

二分法又称分半法，或对分法，是一种方程式根的近似值求法.一般在计算机竞赛中经常使用，为基础算法。二分法有经常做为许多算法的优化途径，可以使一些0(n)的算法优化成0(log(n))。

12.2.2 基本思想

二分法的思想：分而治之。将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同，(如果子问题的规模仍然不够小，则再划分为k个子问题),然后递归的求解这些子问题，最后用适当的方法将各子问题的解合并成原问题的解。

12.2.3 基本特征

二分法所能解决的问题一般具有以下几个特征：

(1)该问题的规模缩小到一定的程度就可以容易地解决

(2)该问题可以分解为若干个规模较小的相同问题

(3)该问题所分解出的各个子问题是相互独立的

(4)利用分解出的子问题的解可以合并为该问题的解

12.2.4 二分搜索算法介绍

前提条件：有一组数已经按从小到大(或从大到小)排序

目标：输入一个数x，在这组数查找是否有x

二分搜索的步骤：

确定三个关键下标的初值：bott=0, top=8, mid=(bott+top)/2;

判断要找的数x是否等于a[mid] 

①x==a[mid]  找到，结束

②x<a[mid]  在a[bott]—a[mid-1]之间继续查找x

                top=mid-1;  mid=(bott+top)/2;

③ x>a[mid]  在a[mid+1]—a[top]之间继续查找x

                bott=mid+1;  mid=(bott+top)/2; 

二分实例介绍：设在数组a中顺序放了以下9个元素：

检索x=9。Left=0,right=8,mid=(left+right)/2=4;

 9==a[4], 一次比较就成功, 最好情况。

检索x=-15。Left=0,right=8,mid=(left+right)/2=4;

 -15<a[4],right=mid-1=3,mid=(left+right)/2=1;

 -15<a[1]。Left=0,right=mid-1=0,mid=(left+right)/2=0;

 -15==a[0], 3次比较,成功

二分查找代码：

#include<stdio.h>#define  N  10int a[N];int find(int x, int left, int right){  while(left<=right)  {    int mid=(left+right)/2;    if(a[mid]==x)      return mid;    else if(a[mid]>x)      right=mid-1;    else left=mid+1;  }  return -1;}int main( ){  int x,index; 	 PRintf("请从小到大输入10个数/n");  for(int i=0;i<N;i++)    scanf("%d",&a[i]);  	printf("请输入需要查找的数x/n");    scanf("%d",&x);    index=find(x,0,N);    if(index==-1)      printf("%d is no found!/n",x);    else      printf("find %d==a[%d] !/n",x,index);}