二分查找演算法

A. 二分查找

#include <stdio.h>

int BinarySearch(int * R,int n,int key) // 在長度為n的數組R中查找關鍵字key
{
int low=0,high=n-1,mid;
while(low<=high)
{
mid=(low+high)/2;
if(key<R[mid])
{
printf("R[mid]=%d <\n",R[mid]);
high=mid-1;
}
else if(key>R[mid])
{
printf("R[mid]=%d >\n",R[mid]);
low=mid+1;
}
else
{
printf("R[mid]=%d =\n",R[mid]);
return mid; // 返回查找到的索引值
}
}
return -1;
}

void main()
{
int R[]={1,2,3,5,7,8,10,15,16,17,19,20};
printf("%d\n",BinarySearch(R,12,17)); // 測試在數組R中查找17,並輸出索引號
}

B. 二分查找法

總共13個，從0開始，最大是12，使用二分法原則分析如下
第一次：12/2=6 , (6)=45<90
第二次:(7+12)/2=9,(9)=77<90
第三次:(10+12)/2=11,(11)=95>90
第四次:((11-1)+10)/2=10,(10)=90 查找成功

C. C#二分查找演算法

二分查找的基本思想是：（設R[low..high]是當前的查找區間）
（1）首先確定該區間的中點位置：mid=(low+high)/2
（2）然後將待查的K值與R[mid].key比較：若相等，則查找成功並返回此位置，否則須確定新的查找區間，繼續二分查找
// Source：
public int search(int[] q)
{
int i, low = 0, high = q.Length - 1, middle;
Console.Write("請輸入想要查找的數字:");
i=int.Parse(Console.ReadLine());
while (low <= high)
{
middle = (low + high) / 2;
if (i == q[middle])return i;
if (i < q[middle])high = middle - 1;
else low = middle + 1;
}
throw new Exception("數組中不存在這個數。");
}

D. C語言 二分查找演算法 用遞歸實現 我改動了一下

本人直接打出來的，並未在平台上編譯運行過，所以可能會有語法錯位，還請自行調試更改
#include<stdio.h>

int RecorBinarySearch(int a[], int, int, int);
int main(void)
{
int i=0, n, m, key;
int a[10000], c[10000];

scanf("%d", &n);
scanf("%d", &m);

printf("提示：輸入%d個整數且必須按升序排列。\n", n);
for(i=0; i<n; i++){
scanf("%d", &a[i]);
}
printf("提示：輸入%d個預查找的數。\n", m);
for(i=0; i<m; i++){
scanf("%d", &key);
c[i] = RecorBinarySearch(a, key, 0, n-1);
}
printf("提示：輸出預查找的數在數組中的位置。（-1代表未找到）\n");
for(i=0; i<m; i++) {
printf("%d ", c[i]);
}
return 0;
}

int RecorBinarySearch(int a[], int key, int low, int high)
{
int nRet;
if(low > high)
nRet = -1;
else {
int mid = (high + low) / 2;
if(key == a[mid])
nRet = mid;
else if(key > a[mid])
nRet = RecorBinarySearch(a, key, mid+1, high);
else if(key < a[mid])
nRet = RecorBinarySearch(a, key, low, mid-1);
}
return nRet;
}

E. 二分查找的演算法復雜度

二分查找的基本思想是將n個元素分成大致相等的兩部分，取a[n/2]與x做比較，如果x=a[n/2],則找到x,演算法中止；如果x<a[n/2],則只要在數組a的左半部分繼續搜索x,如果x>a[n/2],則只要在數組a的右半部搜索x.
時間復雜度無非就是while循環的次數！
總共有n個元素，
漸漸跟下去就是n,n/2,n/4,....n/2^k（接下來操作元素的剩餘個數），其中k就是循環的次數
由於你n/2^k取整後>=1
即令n/2^k=1
可得k=log2n,（是以2為底，n的對數）
所以時間復雜度可以表示O()=O(logn)
下面提供一段二分查找實現的偽代碼:
BinarySearch(max,min,des)
mid-<(max+min)/2
while(min<=max)
mid=(min+max)/2
if mid=des then
return mid
elseif mid >des then
max=mid-1
else
min=mid+1
return max
折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用O(log n)完成搜索任務。它的基本思想是，將n個元素分成個數大致相同的兩半，取a[n/2]與欲查找的x作比較，如果x=a[n/2]則找到x，演算法終止。如 果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右 半部繼續搜索x。

F. 用二分查找演算法查詢某學生成績

/*這是我自己寫的二分查找演算法，用遞歸實現：在已按非降序排序的數組arr[0..length-1]中從位置startPos到endPos查找num這個值，返回值為下標的值，若沒找到則返回-1。*/
int binarySearch(int *arr,int num,int startPos,int endPos)
{
if((startPos >= endPos) && (*(arr+startPos) != num))
{
return -1;
}
else
{
int j = (startPos+endPos)/2;

if(*(arr+j) == num)
{
return j;
}
else
{
if(*(arr+j) > num)
{
return binarySearch(arr,num,startPos,j-1);
}
else
{
return binarySearch(arr,num,j+1,endPos);
}
}
}
}

G. 如果數據分布不均勻，怎麼優化二分查找演算法

樓主是不是想求出一個最小半徑的圓，圓內包含所有的點？這個問題很有趣。

尋找這個圓的時候注意一下幾點：
1.這個圓必然穿過圖中某些靠外圍的點，這樣才是最小半徑的圓。
2.幾何中我們知道，三個點可以確定一個圓, 我們就是需要找出這三個點來.

演算法如下：1.先求這些點對應的凸包，已經有現成的演算法。
2.生成凸包後，在看凸包上哪三點確定的圓可以包含凸包。

當然如果樓主討論的不是以上所述，而是模式分類的話，建議看看數據分類方法。可以搜索關鍵字：Gaussian mixtrual model, expectation-maximization algorithm 和 k-mean algorithm 學習下相關的知識。

H. 二分查找演算法

前提要求數據排好序，有遞歸和非遞歸版本
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;
}

I. 對比順序查找,二分查找和哈希查找演算法,它們各自的特點是什麼

順序查找,二分查找和哈希查找演算法,它們各自的特點是：
1.對比順序查找的特點就是從表的第一個元素開始一個一個向下查找，如果有和目標一致的元素，查找成功;如果到最後一個元素仍沒有目標元素，則查找失敗。
2.二分查找的特點就是從表中間開始查找目標元素。如果找到一致元素，則查找成功。如果中間元素比目標元素小，則仍用二分查找方法查找表的後半部分(表是遞增排列的)，反之中間元素比目標元素大，則查找表的前半部分。
3.哈希演算法的特點是是使用給定數據構造哈希表，然後在哈希表上進行查找的一種演算法。先給定一個值，然後根據哈希函數求得哈希地址，再根據哈希地址查找到要找的元素。是通過數據元素的存儲地址進行查找的一種演算法。