1. BM17 二分查找

?? 要求：給定一個 元素升序的、無重復數字的整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標（下標從 0 開始），否則返回 -1。

輸入：[-1,0,3,4,6,10,13,14],13
返回值：6
說明：13     出現在nums中并且下標為6   

1.1 自己的整體思路

1. 使用二分法，先定義三個指針，左指針，右指針，中間指針。
2. 比較中間指針對應數值與目標數值是否相等，如果相等直接返回該點索引；如果目標值大于中間值，則移動左指針，另其為中間指針加上1；如果目標值小于中間值，則移動右指針，另其為中間指針減1。
3. 直到左指針大于右指針，結束整個循環，這時是沒有找到與目標值對應的索引的。

#include <stdbool.h>
#include <stdlib.h>
int search(int* nums, int numsLen, int target ) {// write code hereint n_pre = 0;                           //首指針位置int n_next = numsLen - 1;                //尾部指針位置int n_mid = (n_pre + n_next) / 2;        //中間指針位置if (numsLen == 0) {                      //數組為空的情況return -1;}while ( nums[n_mid] != target ) {        //中間值是否等于目標值if ( nums[n_mid] < target) {         //目標值在中間右側n_pre = n_mid + 1;                //更新左索引n_mid = (n_pre + n_next)/2;       //更新中間索引}else {n_next = n_mid - 1;                //更新右索引n_mid = (n_pre + n_next)/2;       //更新中間索引}if ( n_pre > n_next ) {                //左指針大于右指針,結束整個循環return -1;}}return n_mid;
}

??開始上面的結束條件寫成了這樣的了：

    if ( n_pre == n_next ) {                  //沒有找到，最終兩個索引會重合   會出現在右邊的情況，不是一直到最后都會重合的if (nums[n_pre ] == target) {return n_pre ;}else {return -1;}}

??認為兩個指針一定會重合，只要判斷重合時候的情況就能結束整個循環,但是未通過所有的測試。

1.2 其他的方法（標準判斷方法）

??判斷條件是左索引是否大于右索引。

int search(int* nums, int numsLen, int target ) {// write code hereif(numsLen == 0) return -1;int left=0, right=numsLen-1;while(left<=right) {int mid = left+(right-left)/2;if(nums[mid]==target) return mid;if(nums[mid]<target) left=mid+1;if(nums[mid]>target) right=mid-1;}return -1;
}

2. BM21 旋轉數組的最小數字

?? 要求：有一個長度為 n 的非降序數組，比如[1,2,3,4,5]，將它進行旋轉，即把一個數組最開始的若干個元素搬到數組的末尾，變成一個旋轉數組，比如變成了[3,4,5,1,2]，或者[4,5,1,2,3]這樣的。請問，給定這樣一個旋轉數組，求數組中的最小值。

輸入：[3,4,5,1,2]
返回值：1

??這個題開始使用的分類討論的情況，情況太多了，最后也沒有寫出來，下面是參考大佬的寫法：
核心思想：

1.計算中間位置 mid，并與 right 指針所指向的元素進行比較：
?如果 rotateArray[mid] > rotateArray[right]，說明最小值在 mid 右側，將 left 更新為 mid + 1。
?如果 rotateArray[mid] < rotateArray[right]，說明最小值在 mid 左側或就是 mid，將 right 更新為 mid。
?如果 rotateArray[mid] == rotateArray[right]，無法確定最小值在哪一側，但是可以排除 right 指針所指向的元素，將 right 向前移動一位，縮小搜索范圍。
2. 循環繼續，直到 left 和 right 指針相鄰或重合。最終，right 指向的位置即為最小值所在位置。

int minNumberInRotateArray(int* rotateArray, int rotateArrayLen ) {int left=0, right=rotateArrayLen-1;while(left<right) {int mid = left+(right-left)/2;if(rotateArray[mid]>rotateArray[right]) left=mid+1;         //說明最小值在右邊else if(rotateArray[mid]<rotateArray[right]) right=mid;     //說明最小值在左邊else right--;    //22212或者10111                            //不能說明在左邊還是右邊，但是肯定不是右值，索引減去1再進行比較                        //關注右邊，從右邊出發}return rotateArray[right];
}

3. BM23 二叉樹的前序遍歷

?? 要求：給你二叉樹的根節點 root ，返回它節點值的前序遍歷。
????????????????????

輸入：{1,#,2,3}
返回值：[1,2,3]

3.1 自己的整體思路

1. 使用二叉樹的前序遍歷方法，遞歸完成二叉樹元素的訪問。
2. 這里訪問二叉樹的元素，需要傳一個變量（接收數組的索引地址），因為最后結果需要返回該索引值。

具體代碼如下：

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
void visit_root(struct TreeNode* p ,int *arr, int *a){         //訪問二叉樹的元素，存到數組中去*(arr + *a) = p->val;//arr[*a] = p->val;    //寫成這樣也是可以的// *a++;               //這樣是錯的，優先級不一樣，++的優先級要高(*a)++;          //索引加1}void  Preorder(struct TreeNode* p , int *arr, int *a){        //遍歷二叉樹if (p != NULL) {visit_root(p , arr, a);Preorder(p->left,  arr, a);    //遞歸左子結點         //這行代碼為空的時候，才會運行到下一行Preorder(p->right, arr, a );   //遞歸右子結點}
}
int* preorderTraversal(struct TreeNode* root, int* returnSize){//前序遍歷 先根，再左，再右struct TreeNode* cur =  root;                           //接收根結點int*  result = (int *)malloc(100 * sizeof(int));        //申明一個100的空數組int a = 0;                                              //接收數組的索引int *i = &a;                                            //接收a的地址Preorder(cur, result, i);                               //遍歷二叉樹 *returnSize = *i;                                       //必須給行號 ，卡了半天return result;
}

3.2 大佬的方法

1. 先判斷二叉樹有多少元素，這樣再動態申請多大的內存。
2. 遍歷二叉樹即可。

int TreeSize(struct TreeNode* root)
{if(root==NULL){return 0;}return TreeSize(root->left)+TreeSize(root->right)+1;
}
void preorder(struct TreeNode* root, int* a,int *i) 
{if(root==NULL){return ;}a[*i]=root->val;++(*i);preorder(root->left,a,i);preorder(root->right,a,i); 
}
int* preorderTraversal(struct TreeNode* root, int* returnSize ) 
{  int i=0; int size=TreeSize(root);int* a=(int*)malloc(size*sizeof(int));preorder(root,a,&i);*returnSize=size;return a;
}

3.3 小結

3.3.1 malloc函數

?? malloc（memory allocation）函數是用于動態分配內存的標準庫函數之一。它是在程序運行時從堆（heap）中申請一塊指定大小的內存空間，以供程序使用。
?? malloc函數的原型如下：
size：要分配的內存空間的大小，以字節為單位。通常使用sizeof運算符來計算要分配的空間大小，以確保正確性。
返回值：malloc函數返回一個void指針，指向已分配內存塊的起始地址。由于返回類型是void *，您需要將這個通用指針轉換為適當類型的指針，然后才能訪問和操作分配的內存。

void *malloc(size_t size);

?? 舉例分配一個包含10個int元素的數組:

 int *array = (int *)malloc(10 * sizeof(int));

注意：

1. malloc分配的內存塊是未初始化的，其中的值是不確定的。您應該確保在使用之前將其初始化。
2. 在使用完分配的內存后，必須使用free函數釋放它，以避免內存泄漏。
3. 在調用malloc后，應該檢查返回的指針是否為NULL，以防止內存分配失敗。
4. malloc函數分配的內存是在堆上，與局部變量不同，不會在函數退出后銷毀，需要手動釋放。

3.3.2 *和++的優先級

++操作符的優先級比*操作符更高，因此會先執行++操作，然后再執行*操作。下面的a是一個int型變量指針
*a++;       //指針會往下加1，再去該地址里面的值，地址變了
(*a)++;     //取指針a對應的變量值，把變量值加1，地址沒變