二分查找

limitsy · limitsy · commit 636d6d1c159a · 2019-05-04T16:34:20.000+08:00
diff --git a/notes/数据结构与算法.md b/notes/数据结构与算法.md
@@ -132,9 +132,45 @@ https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490
 
 #### 二分查找法
 
-#### 二叉树遍历
+在有序表中，通过不断的二分判断mid与目标是否一致，并缩小目标所在区间。
 
-### 4.. 二分搜索树
+**代码实现**
+
+```java
+// 非递归实现
+private static int search(int[] data, int l, int r, int target) {
+    int mid;
+    while(l < r) {
+        mid = (l + r) / 2;
+        if(data[mid] == target) {
+            return mid;
+        } else if(data[mid] < target) {
+            l = mid + 1;
+        } else {
+            r = mid;
+        }
+    }
+    return -1;
+}
+// 递归实现
+private static int searchDfs(int[] data, int l, int r, int target) {
+    if(l >= r) {
+        return -1;
+    }
+    int mid = (l + r) / 2;
+    if(target == data[mid]) {
+        return mid;
+    } else if(target > data[mid]) {
+        return searchDfs(data, mid + 1, r, target);
+    } else {
+        return searchDfs(data, l, mid, target);
+    }
+}
+```
+
+##### 
+
+### 4.. 二叉树遍历
 
 #### 深度优先遍历（前序、中序、后序遍历）
 
