🥰歡迎關注?輕松拿捏C語言系列，來和 小哇 一起進步！?

🌈感謝大家的閱讀、點贊、收藏和關注💕

---

目錄🎉

?一、介紹🌈

二、步驟🌙

三、代碼??

---

?

?一、介紹

二分查找是一種在有序數組中查找某一特定元素的搜索算法。

舉個生活中的例子，當我們要去圖書館借書時，知道了要找的圖書編號，我們可以在一個大致范圍的中間查找，然后在決定往前找還是往后找。這樣就能比一本一本地找更加快速。

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

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

如果在某一步驟數組為空，則代表找不到。這種搜索算法每一次比較都使搜索范圍縮小一半。

二、步驟

1. 確定搜索范圍，即數組的下標范圍left和right。
2. 計算中間元素的下標mid = (left + right) / 2(注意整數除法）。

? ? ? ??但是像這樣求平均值，如果數字太大了超過int類型能表示的最大范圍，這種算法就會有問題，整數會溢出。

? ? ? ? 所以我們可以換一個思路，把兩數的差值的一半 加到另一個數字中：

? ? ? ? mid = left + (right-left) /2?

1. 判斷中間元素與目標值的大小關系。

   • 如果相等，則返回中間元素的下標。
   • 如果目標值小于中間元素，則在左半部分繼續搜索（right = mid - 1）。
   • 如果目標值大于中間元素，則在右半部分繼續搜索（left = mid + 1）。
   • 如果搜索范圍left大于right，則表示數組中沒有目標值，返回-1或其他表示未找到的值。

三、代碼

法一：用遞歸實現

#include <stdio.h>  int Sort(int arr[], int left, int right, int Key) {  if (left > right) return -1; // 搜索范圍無效  int mid = left + (right - left) / 2;  //這種寫法可避免溢出if (arr[mid] == Key) {  return mid; // 找到目標，返回下標  } else if (arr[mid] > Key) {  return Sort(arr, left, mid - 1, Key); // 在左半部分繼續搜索  } else {  return Sort(arr, mid + 1, right, Key); // 在右半部分繼續搜索  }  
}  int main() {  int arr[] = {1, 3, 5, 7, 9};  int key = 5;  int n = sizeof(arr) / sizeof(arr[0]);  int ret = Sort(arr, 0, n - 1, key);  if (ret != -1) {  printf("元素 %d 在數組中的下標為 %d\n", key, ret);  } else {  printf("元素 %d 不在數組中\n",key);  }  return 0;  
}

法二：用循環實現

#include <stdio.h>  int Sort(int arr[], int N, int Key) 
{  int left = 0;int right = N - 1;  while (left <= right) {  int mid = left + (right - left) / 2;  if (arr[mid] == Key) {  return mid;  } else if (arr[mid] > Key){  right = mid - 1;  }else{  left = mid + 1;  }  }  return -1; // 未找到目標值  
}  int main()
{  int arr[] = {1, 3, 5, 7, 9};  int key = 5;  int n = sizeof(arr) / sizeof(arr[0]);  int ret = Sort(arr, n, key);  if (ret != -1) {  printf("元素 %d 在數組中的下標為 %d\n", key, ret);  } else {  printf("元素 %d 不在數組中\n",key);  }  return 0;   
}

使用循環的方式來實現二分查找，更直觀且易于理解。

不過，遞歸的方式在某些情況下可能更簡潔。

無論使用哪種方式，都需要確保數組是有序的，因為二分查找的前提是有序數組。?

---

?

?🎉🎉🎉本文內容結束啦，希望各位大佬多多指教！

🌹🌹感謝大家三連支持

💕敬請期待下篇文章吧~