二分搜索演算法
『壹』 二分搜索演算法
#include <stdio.h>
#include <stdlib.h>
int a[100]={1,2,3,5,12,12,12,15,29,55};//數組中的數（由小到大）
int k;
void found(int &x,int &y,int k) //在x與y之間，要找k
{
if(x>y)return;
int m=x+(y-x)/2;
if(a[m]==k)x=y=m;
else if(a[m]>k)found(x,y=m-1,k);//找左邊
else found(x=m+1,y,k);//找右邊
}
int main()
{ int i=0,j=9;
scanf("%d",&k);//輸入要找的數字k
found(i,j,k);//從數組a[0]到a[9]中找k
if(i==j)printf("a[%d]==%d ",i,k);
else printf("a[%d]==%d a[%d]==%d, k==%d ",j,a[j],i,a[i],k);
return 0;
}
『貳』 二分搜索演算法是利用什麼實現的演算法
根據分治策略來實現
『叄』 C語言遞歸函數如何實現二分搜索演算法
折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，已知一個有n個元素的有序序列, 將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x, 直到找到x或者是沒有找到!
如果是常規的方法的話那麼我們可以通過循環的方式, 按照上面說的演算法, 找到則退出循環, 否則繼續循環直到左下標位置小於或者等於右下標的位置.
按兄弟你的意思是要用遞歸方法進行搜索, 那麼大概還是上面的演算法, 只是把循環的方式改成遞歸方式: 如果沒找到,則確定新的搜索范圍, 即左右下標新位置, 然後把新的參數傳給函數繼續調用函數進行遞歸搜索!!
遞歸方式實現詳細代碼如下:
#include <stdio.h>
#define ARRAY_SIZE 10
#define NOT_FOUND -1
int BinarySearch(int array[], int left, int right, int NumToSearch)
{
int mid = (left + right) / 2;
if (left <= right)
{
if (NumToSearch == array[mid])
{
return mid;
}
else if (NumToSearch < array[mid])
{
right = mid - 1;
return BinarySearch(array, left, right, NumToSearch);
}
else
{
left = mid + 1;
return BinarySearch(array, left, right, NumToSearch);
}
}
return NOT_FOUND;
}
int main()
{
int a[ARRAY_SIZE] = {2, 5, 6, 7, 13, 20, 22, 27, 112, 222};//假設一個已知的有序且是升序數列
int result = 0;//查找的結果
int x = 13;//假設我們要查找的數是13
int left = 0;//序列開始下標
int right = ARRAY_SIZE - 1;//序列結尾下標
result = BinarySearch(a, left, right, x);
if (result == NOT_FOUND)
{
printf("Not Found!\n");
}
else
{
printf("Found %d in array a, it is a[%d]\n", x, result);
}
return 0;
}
希望對兄弟你有幫助!
『肆』 二分搜索演算法的實現
二分搜索的時候，是要慢慢縮小搜索范圍的。比如一共有10個，那麼middle是5,下一層搜索的范圍應該是1-4和6-10。你的函數里沒有這個功能。搜索函數至少應該是int BinarySearch(Type a[], const Type& x,int left, int right);終止條件就是if(left > right) 你定義y的時候是在main函數里，所以BinarySearch裡面不能直接用y，解決方式是在外部定義一個全局的y變數，或者把y變數傳到函數里。
『伍』 實現二分搜索演算法,並分析其時間復雜度
對於這樣一個謂詞f()，滿足性質：若f(a)=true，則對於任意定義域內的b>a，f(b)=true.
l與r為值域
int work ( int begin , int end ) {
while ( end - begin != 1 ) {
const int middle = ( begin + end ) / 2 ;
if ( f ( middle ) ) end = middle ;
else begin = middle ;
}
return begin ;
}
返回的是最大的x使f(x)為否
『陸』 改寫二分搜索演算法
小於x的最大元素在x的左邊（x不存在時），大於x的最小元素在x的右邊（x不存在時）；所以比較到最後，如果找到x，則輸出x的位置，沒找到x時，返回最後的位置的左和右位置
#include <stdio.h>
int main(){
int ip[100],n,key,i,mid,lt=0,rt,fg=0;
printf("請輸入數組長度：");
scanf("%d",&n);
printf("請輸入已排序的數組：");
for(i=0;i<n;i++)
scanf("%d",ip+i);
printf("請輸入待查找數：");
scanf("%d",&key);
rt=n-1;mid=n/2;
while(mid!=lt)
{
if(ip[mid]==key)
{
fg=1;
break;
}
else
if(ip[mid]>key)
{
rt=mid;
mid=(lt+mid)/2;
}
else
{
lt=mid;
mid=(rt+mid)/2;
}
}
if(fg)
printf("%d\n",mid+1);
else
printf("%d %d\n",mid+1,mid+2);
return 0;
}
『柒』 二分搜索問題
vara:array[1..10]ofinteger;i,j,n,x:integer;beginwriteln('輸入10個從小到大的數：');fori:=1to10doread(a[i]);writeln('輸入要查找的數：');readln(x);i:=1;n:=10;j:=trunc((i+n)/2);repeatifa[j]>xthenbeginn:=j-1;j:=trunc((i+j)/2)endelseifa[j]=n);{為什麼是這個結束循環條件}ifa[j]=xthenwriteln('查找成功！位置是：',j:3)elsewriteln('查找失敗，數組中無此元素！')end.
『捌』 二分查找演算法
前提要求數據排好序，有遞歸和非遞歸版本
int binSearch(const int *Array,int start,int end,int key)
{
int left,right;
int mid;
left=start;
right=end;
while (left<=right) { /注釋中為遞歸演算法，執行效率低，不推薦
mid=(left+right)/2;
/* if (key<Array[mid]) {
return(binSearch(Array,left,mid,key));
}
else if(key>Array[mid]){
return (binSearch(Array,mid+1,right,key));
}
else
return mid;
*/
if (key<Array[mid]) {
right=mid-1;
}
else if(key>Array[mid]){
left=mid+1;
}
else
return mid;
}
return -1;
}
『玖』 用c++語言實現二分搜索演算法
這個就是二分法排序函數的源代碼 傳入參數是數組a和數組的大小n
template <class T>
void BinSort( T a[], int n ) {
int low,high,mid;
for (int i=1; i<n; i++) {
T t=a[i];
low=0; high=i-1;
while (low<=high) {
mid=(low+high)/2;
if (a[mid]>t) high=mid-1;
else low=mid+1;
}
for (int j=i-1; j>=high+1; j--) a[j+1]=a[j];
a[high+1]=t;
}
}