二分查找演算法數據結構完整代碼

『壹』 二分查找法的具體演算法

折半查找法也稱為二分查找法，它充分利用了元素間的次序關系，採用分治策略，可在最壞的情況下用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)。在數據量很大的時候，它的線性查找在時間復雜度上的優劣一目瞭然。

『貳』 用遞歸方法寫出有序數組的二分查找演算法

什麼是二分查找？

二分查找也稱折半查找（Binary Search），它是一種效率較高的查找方法。但是，折半查找要求線性表必須採用順序存儲結構，而且表中元素按關鍵字有序排列。

二分查找優缺點

優點是比較次數少，查找速度快，平均性能好；

其缺點是要求待查表為有序表，且插入刪除困難。

因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。
使用條件：查找序列是順序結構，有序。

過程

首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重復以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

利用循環的方式實現二分法查找

public class BinarySearch {
public static void main(String[] args) {
// 生成一個隨機數組 int[] array = suiji();
// 對隨機數組排序 Arrays.sort(array);
System.out.println("產生的隨機數組為： " + Arrays.toString(array));

System.out.println("要進行查找的值： ");
Scanner input = new Scanner(System.in);
// 進行查找的目標值 int aim = input.nextInt();

// 使用二分法查找 int index = binarySearch(array, aim);
System.out.println("查找的值的索引位置： " + index);

}

/** * 生成一個隨機數組 *
* @return 返回值，返回一個隨機數組 */
private static int[] suiji() {
// random.nextInt(n)+m 返回m到m+n-1之間的隨機數 int n = new Random().nextInt(6) + 5;
int[] array = new int[n];
// 循環遍歷為數組賦值 for (int i = 0; i < array.length; i++) {
array[i] = new Random().nextInt(100);
}
return array;
}

/** * 二分法查找 ---循環的方式實現 *
* @param array 要查找的數組 * @param aim 要查找的值 * @return 返回值，成功返回索引，失敗返回-1 */
private static int binarySearch(int[] array, int aim) {
// 數組最小索引值 int left = 0;
// 數組最大索引值 int right = array.length - 1;
int mid;
while (left <= right) {
mid = (left + right) / 2;
// 若查找數值比中間值小，則以整個查找范圍的前半部分作為新的查找范圍 if (aim < array[mid]) {
right = mid - 1;
// 若查找數值比中間值大，則以整個查找范圍的後半部分作為新的查找范圍 } else if (aim > array[mid]) {
left = mid + 1;
// 若查找數據與中間元素值正好相等，則放回中間元素值的索引 } else {
return mid;
}
}
return -1;
}}
運行結果演示：

總結：

遞歸相較於循環，代碼比較簡潔，但是時間和空間消耗比較大，效率低。在實際的學習與工作中，根據情況選擇使用。通常我們如果使用循環實現代碼只要不是太繁瑣都選擇循環的方式實現~

『叄』 數據結構折半查找演算法的方法

041424344#include <stdio.h> int Dichotomy(int a[],int _value,int n){ // 二分法(也稱折半查找法) int index=0; // 當前數組的首元素下標 int current=n-1; // 數組當前的大小 int k; // 當前數組中間的數的下標 while (index<current) { // 開始二分法查找 k=(index+current)/2; // 除以2代表得到當前數組中間的數的下標 if(a[k]==_value) return k; // 返回要查找的值_value所在的下標 // 否則比較要查找的值_value是在折半後的前半部分還是後半部分 if(a[k]<_value){ // 說明要查找的值在折半後的後半部分 index=k+1; // 令index指向後半部分數組的首元素 } else{ // 說明要查找的值在折半後的前半部分 current=k-1; // 令current等於前半部分數組的長度 } } return -1; // 返回-1代表沒有查找到該值(_value)}void main(){ int arr[5]={2,12,45,87,95};// 前提是一組數組必須是有序數對(即按小到大或大到小) if(Dichotomy(arr,87,5)!=-1) printf("87在數組中對應的下標是:%d\n",Dichotomy(arr,87,5)); else printf("沒有找到指定的值\n");}// 用一句話概括二分法(折半查找法)的思想就是:在一組有序對數組中反復折半後得到中間數組的下標,然後再進行是否與要查找的值相等,若相等則返回當前要查找的值的下標。 那麼，上面的代碼的注釋與下面一一對應，它在執行的結果會產生兩種情況，第一種,不存在。第二種，存在。先來說說第一種情況 不存在： 1.如果給定要查找的值_value大於數組中最大的數,則index不斷增大從而促使while循環終止 2.如果給定要查找的值_value小於數組中最小的數,則current不斷減少從而促使while循環終止(你自己可以動手在紙上畫一個數組,然後思路跟著代碼走就會知道或設單步調試亦可) 第二種情況 存在： 1.要查找的數_value正好是在數組中間.那麼就執行了一次循環,當然這也是最理想的效果. 否則反復執行2和3:2.如果要查找的數_value不存在中間,則判斷它是否大於中間的數還是小於中間的數,如果小於中間的數則說明_value應該在數組中間的前半部分,那麼current=k-1(即令current等於前半部分的長度),然後仍然採取折半的方法,反復此操作直至找到該數的下標為止. 3.如果要查找的數_value不存在中間,則判斷它是否大於中間的數還是小於中間的數,如果大於中間的數則說明_value應該在數組中間的後半部分,那麼index=k+1(即令index指向後半部分的第一個下標),然後仍然採取折半的方法,反復此操作直至找到該數的下標為止.

『肆』 什麼叫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);
}

『伍』 如下為二分查找的非遞歸演算法，試將其填寫完整。

遞歸演算法是一種分而治之的方法，簡單的說就是調用自己本身；能把復雜的問題化為簡單臘培段來解決；但是執行的效率比較低，所以一般分析問題輪譽用遞歸，實際解決問題中源用非遞歸。

『陸』 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("數組中不存在這個數塌肢。");
}

『柒』 二分查找的代碼怎麼寫

以下是四個二分查找代碼的 Python 實廳鎮喚現：
①在扮凱升序數組中查找第一個>=x的元素的下標，查找右邊界
def binary_search_right_bound_ascending(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] < x:
left = mid + 1
else:
right = mid - 1
if left >= len(arr) or arr[left] != x:
return -1
return left

②在降序數組中查找第一個>=x的元素的下標，查找右邊界
def binary_search_right_bound_descending(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] > x:
left = mid + 1
else:
right = mid - 1
if left >= len(arr) or arr[left] != x:
return -1
return left

③在升序數組中查找第一個<=x的元素的下標，查找右邊界
def binary_search_left_bound_ascending(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) /旅純/ 2
if arr[mid] > x:
right = mid - 1
else:
left = mid + 1
if right < 0 or arr[right] != x:
return -1
return right

④在降序數組中查找第一個<=x的元素的下標，查找右邊界
def binary_search_left_bound_descending(arr, x):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] < x:
right = mid - 1
else:
left = mid + 1
if right < 0 or arr[right] != x:
return -1
return right

注意：在所有代碼中，如果找不到符合條件的元素，會返回 -1。

『捌』 二分查找的演算法復雜度

二分查找的基本思想是將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。

『玖』 用二分查找演算法查詢某學生成績

/*這是我自己寫的二分查找演算法，用遞歸實現：在已按非降序排序的數組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);
}
}
}
}

『拾』 C語言編寫數據結構查找演算法

實驗五 查找的實現
一、 實驗目的
1．通過實驗掌握查找的基本概念；
2．掌握順序查找演算法與實現；
3．掌握折半查找演算法與實現。
二、 實驗要求
1． 認真閱讀和掌握本實驗的參考程序。
2． 保存程序的運行結果，並結合程序進行分析。
三、 實驗內容
1、建立一個線性表，對表中數據元素存放的先後次序沒有任何要求。輸入待查數據元素的關鍵字進行查找。為了簡化演算法，數據元素只含一個整型關鍵字欄位，數據元素的其餘數據部分忽略不考慮。建議採用前哨的作用，以提高查找效率。
2、查找表的存儲結構為有序表，輸入待查數據元素的關鍵字利用折半查找方法進行查找。此程序中要求對整型量關鍵字數據的輸入按從小到大排序輸入。
一、順序查找
順序查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請輸入您想輸入的%d個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
inti=0;
s->r[s->length].key=k;
while(s->r[i].key!=k)
{

i++;
}
if(i==s->length)
{
printf("該表中沒有您要查找的數據！\n");
return-1;
}
else
returni+1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
順序查找的運行結果：
二、折半查找
折半查找代碼：
#include"stdio.h"
#include"stdlib.h"
typedef struct node{
intkey;
}keynode;
typedef struct Node{
keynoder[50];
intlength;
}list,*sqlist;
int Createsqlist(sqlist s)
{
inti;
printf("請輸入您要輸入的數據的個數:\n");
scanf("%d",&(s->length));
printf("請由大到小輸入%d個您想輸入的個數據;\n\n",s->length);
for(i=0;i<s->length;i++)
scanf("%d",&(s->r[i].key));
printf("\n");
printf("您所輸入的數據為:\n\n");
for(i=0;i<s->length;i++)
printf("%-5d",s->r[i].key);
printf("\n\n");
return1;
}
int searchsqlist(sqlist s,int k)
{
intlow,mid,high;
low=0;
high=s->length-1;
while(low<=high)
{
mid=(low+high)/2;
if(s->r[mid].key==k)
returnmid+1;
elseif(s->r[mid].key>k)
high=mid-1;
else
low=mid+1;
}
printf("該表中沒有您要查找的數據!\n");
return-1;
}
sqlist Initlist(void)
{
sqlistp;
p=(sqlist)malloc(sizeof(list));
if(p)
returnp;
else
returnNULL;
}
main()
{
intkeyplace,keynum;//
sqlistT;//
T=Initlist();
Createsqlist(T);
printf("請輸入您想要查找的數據的關鍵字:\n\n");
scanf("%d",&keynum);
printf("\n");
keyplace=searchsqlist(T,keynum);
printf("您要查找的數據的位置為:\n\n%d\n\n",keyplace);
return2;
}
折半查找運行結果：
三、實驗總結：
該實驗使用了兩種查找數據的方法（順序查找和折半查找），這兩種方法的不同之處在於查找方式和過程不同，線性表的創建完全相同，程序較短，結果也一目瞭然。