简介

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

二分查找又称折半查找，它是一种效率较高的查找方法。

二分查找要求：（1）必须采用顺序存储结构 （2）.必须按关键字大小有序排列

---

过程

首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

---

原理

将数组分为三部分，依次是中值（所谓的中值就是数组中间位置的那个值）前，中值，中值后；将要查找的值和数组的中值进行比较，若小于中值则在中值前 面找，若大于中值则在中值后面找，等于中值时直接返回。然后依次是一个递归过程，将前半部分或者后半部分继续分解为三部分。

---

要求

1.必须采用顺序存储结构。

2.必须按关键字大小有序排列。

---

实现

二分查找的实现用递归和循环两种方式

---

代码

• 循环实现

C#代码

public static int Method(int[] nums, int low, int high, int target)
 {
 while (low <= high)
 {
 int middle = (low + high) / 2;
 if (target == nums[middle])
 {
 return middle;
 }
 else if (target > nums[middle])
 {
 low = middle + 1;
 }
 else if (target < nums[middle])
 {
 high = middle - 1;
 }
 }
 return -1;
 }

Python代码

def bin_search(data_list, val): 
 low = 0 # 最小数下标 
 high = len(data_list) - 1 # 最大数下标 
 while low <= high: 
 mid = (low + high) // 2 # 中间数下标 
 if data_list[mid] == val: # 如果中间数下标等于val, 返回 
 return mid 
 elif data_list[mid] > val: # 如果val在中间数左边, 移动high下标 
 high = mid - 1 
 else: # 如果val在中间数右边, 移动low下标 
 low = mid + 1 
 return # val不存在, 返回None
ret = bin_search(list(range(1, 10)), 3)
print(ret)

int BinSearch(SeqList *R，int n,KeyType K)
{
 //在有序表R[0..n-1]中进行二分查找，成功时返回结点的位置，失败时返回-1
 int low=0,high=n-1,mid； //置当前查找区间上、下界的初值
 while(low<=high)
 {
 if(R[low].key==K)
 return low;
 if(R[high].key==k)
 return high; //当前查找区间R[low..high]非空
 mid=low+(high-low)/2;
 /*使用(low+high)/2会有整数溢出的问题
 （问题会出现在当low+high的结果大于表达式结果类型所能表示的最大值时，
 这样，产生溢出后再/2是不会产生正确结果的，而low+((high-low)/2)
 不存在这个问题*/
 if(R[mid].key==K)
 return mid; //查找成功返回
 if(R[mid].key<K)
 low=mid+1; //继续在R[mid+1..high]中查找
 else
 high=mid-1; //继续在R[low..mid-1]中查找
 }
 if(low>high)
 return -1;//当low>high时表示所查找区间内没有结果，查找失败
}

int bsearchWithoutRecursion(int array[],int low,int high,int target)
{
 while(low<=high)
 {
 int mid=low+(high-low)/2;//还是溢出问题
 if(array[mid]>target)
 high=mid-1;
 else if(array[mid]<target)
 low=mid+1;
 else
 return mid;
 }
 return-1;
}

• 递归实现

#include<iostream>
using namespace std;
int a[100]={1,2,3,5,12,12,12,15,29,55};//数组中的数（由小到大）
int k;//要找的数字
int found(int x,int y)
{
 int m=x+(y-x)/2;
 if(x>y)//查找完毕没有找到答案，返回-1
 return -1;
 else
 {
 if(a[m]==k)
 return m;//找到!返回位置.
 else if(a[m]>k)
 return found(x,m-1);//找左边
 else
 return found(m+1,y);//找右边
 }
}
int main()
 {
 cin>>k;//输入要找的数字c语言把cin换为scanf即可
 cout<<found(0,9);//从数组a[0]到a[9]c语言把cout换为printf即可
 return 0;
 }

PHP代码

/*二分查找：前提，该数组已经是一个有序数组，必须先排序，再查找。*/
function binarySearch(&$array,$findVal,$leftIndex,$rightIndex){
$middleIndex=round(($rightIndex+$leftIndex)/2);
if($leftIndex>$rightIndex){
echo'查无此数<br/>';
return;
}
if($findVal>$array[$middleIndex]){
binarySearch($array,$findVal,$middleIndex+1,$rightIndex);
}elseif($findVal<$array[$middleIndex]){
binarySearch($array,$findVal,$leftIndex,$middleIndex-1);
}else{
echo"找到数据:index=$middleIndex;value=$array[$middleIndex]<br/>";
if($array[$middleIndex+1]==$array[$middleIndex]&&$leftIndex<$rightIndex){
binarySearch($array,$findVal,$middleIndex+1,$rightIndex);
}
if($array[$middleIndex-1]==$array[$middleIndex]&&$leftIndex<$rightIndex){
binarySearch($array,$findVal,$leftIndex,$middleIndex-1);
}
}
}