演算法二分搜索畫圖

1. 二分搜索演算法的實現

二分搜索的時候，是要慢慢縮小搜索范圍的。比如一共有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變數傳到函數里。

2. 二分搜索演算法是利用什麼實現的演算法

二分搜索演算法是利用排除剩餘元素中一半的元素實現的演算法。

在計算機科學中，二分搜索（英語：binary search），也稱折半搜索（英語：half-interval search）、對數搜索（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜索演算法。

二分搜索演算法原理：

1、如果待查序列為空，那麼就返回－1，並退出演算法；這表示查找不到目標元素。如果待查序列不為空，則將它的中間元素與要查找的目標元素進行匹配，看它們是否相等。如果相等，則返回該中間元素的索引，並退出演算法；此時就查找成功了。如果不相等，就再比較這兩個元素的大小。

2、如果該中間元素大於目標元素，那麼就將當前序列的前半部分作為新的待查序列；這是因為後半部分的所有元素都大於目標元素，它們全都被排除了。

3、如果該中間元素小於目標元素，那麼就將當前序列的後半部分作為新的待查序列；這是因為前半部分的所有元素都小於目標元素，它們全都被排除了。

3. 二分搜索演算法是利用什麼實現的演算法

二分搜索演算法是分治法裡面的一個特例，叫做減治法

4. 二分查找法的具體演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用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。二分搜索法的應用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜索演算法也不是一件簡單的事。第一個二分搜索演算法早在1946年就出現了，但是第一個完全正確的二分搜索演算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索演算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的，我們可用C++描述如下：

template<class Type>

int BinarySearch(Type a[],const Type& x,int n)

{

int left=0;

int right=n-1;

while(left<=right){

int middle=(left+right)/2;

if (x==a[middle]) return middle;

if (x>a[middle]) left=middle+1;

else right=middle-1;

}

return -1;

}

模板函數BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個演算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。

5. 二分搜索法的簡介

如果x<a[n/2]，則我們只要在數組a的左半部繼續搜索x（這里假設數組元素呈升序排列）。如果x>a[n/2]，則我們只要在數組a的右半部繼續搜索x。二分搜索法的應用極其廣泛，而且它的思想易於理解，但是要寫一個正確的二分搜索演算法也不是一件簡單的事。第一個二分搜索演算法早在1946年就出現了，但是第一個完全正確的二分搜索演算法直到1962年才出現。Bentley在他的著作《Writing Correct Programs》中寫道，90%的計算機專家不能在2小時內寫出完全正確的二分搜索演算法。問題的關鍵在於准確地制定各次查找范圍的邊界以及終止條件的確定，正確地歸納奇偶數的各種情況，其實整理後可以發現它的具體演算法是很直觀的，我們可用C++描述如下：
template<class Type>
int BinarySearch(Type a[],const Type& x,int n)
{
int left=0;
int right=n-1;
while(left<=right){
int middle=(left+right)/2;
if (x==a[middle]) return middle;
if (x>a[middle]) left=middle+1;
else right=middle-1;
}
return -1;
}
或者：
/*找到目標值時返回值為下標，找不到時返回如果要加入此數，應該放置的下標（負數表示）*/
int binarySearch (int arrays[], int size, int num)
{
int low = 0, high = size - 1;
while ( high > low )
{
int mid = (low + high) / 2;
if ( num > arrays[mid] )
low = mid + 1;
else if (num < arrays[mid])
high = mid - 1;
else if (num == arrays[mid])
return mid;
}
return -low - 1;
}
第一個模板函數BinarySearch在a[0]<=a[1]<=...<=a[n-1]共n個升序排列的元素中搜索x,找到x時返回其在數組中的位置，否則返回-1。容易看出，每執行一次while循環，待搜索數組的大小減少一半,因此整個演算法在最壞情況下的時間復雜度為O(log n)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。
二分搜索法的局限性：必須是在有序的元素中進行，不能在無序的元素中使用。

6. 什麼叫java中的二分查找法

1、演算法概念。

二分查找演算法也稱為折半搜索、二分搜索，是一種在有序數組中查找某一特定元素的搜索演算法。請注意這種演算法是建立在有序數組基礎上的。

2、演算法思想。

①搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；

②如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。

③如果在某一步驟數組為空，則代表找不到。

這種搜索演算法每一次比較都使搜索范圍縮小一半。

3、實現思路。

①找出位於數組中間的值，並存放在一個變數中（為了下面的說明，變數暫時命名為temp）；

②需要找到的key和temp進行比較；

③如果key值大於temp，則把數組中間位置作為下一次計算的起點；重復① ②。

④如果key值小於temp，則把數組中間位置作為下一次計算的終點；重復① ② ③。

⑤如果key值等於temp，則返回數組下標，完成查找。

4、實現代碼。

/**
*description:二分查找。
*@paramarray需要查找的有序數組
*@paramfrom起始下標
*@paramto終止下標
*@paramkey需要查找的關鍵字
*@return
*/
publicstatic<EextendsComparable<E>>intbinarySearch(E[]array,intfrom,intto,Ekey)throwsException{
if(from<0||to<0){
("paramsfrom&lengthmustlargerthan0.");
}
if(from<=to){
intmiddle=(from>>>1)+(to>>>1);//右移即除2
Etemp=array[middle];
if(temp.compareTo(key)>0){
to=middle-1;
}elseif(temp.compareTo(key)<0){
from=middle+1;
}else{
returnmiddle;
}
}
returnbinarySearch(array,from,to,key);
}

7. 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;

}

希望對兄弟你有幫助!

8. 改寫二分搜索演算法

小於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;
}

9. 二分搜索技術

public static void main(String[] args) {
int value = 19;
int[] array = new int[]{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int index =0 ,endIndex = array.length-1;
while(index < endIndex-1){
int temp = (endIndex-index+1)/2 + index;
System.out.println("array["+temp+"]="+array[temp]);
if(array[temp]<value){
index = temp+1;
}else if(array[temp]==value){
index = endIndex = temp;
break;
}else{
endIndex = temp;
}
}
System.out.println(array[(int)index]);
}