思路

在有序的数据里面查找，也一定要有序，不一定连续。
很多有序的数据里面精确的定位一个数字，既然是有序的，就对半分，那个要找的数字就在其中一半的，这样就淘汰了另一半数据，一次就淘汰一半的数据，这样不断的一半一半的去掉

可以使用递归的方法，用循环同理

  1. 首先确定该数组中间的下标mid
  2. 然后让需要查找的数key和array[mid]比较
    1. key==array[mid]就找到了
    2. key>array[mid]说明要查找的数在mid右边，需要递归向右查找
    3. key<array[mid]说明要查找的数在mid左边，需要递归向左查找
  3. 找到或者left>right就退出递归

    代码

    ```csharp using System; using System.Collections.Generic;

namespace ConsoleApp1 { class Program { static void Main(string[] args) { int[] arr = new int[8] { 1, 2, 4, 6, 7, 8, 9, 13 }; int index = BinarySearch(arr, 9,0,arr.Length-1); Console.WriteLine(index); } public static int BinarySearch(int[] array, int key,int left,int right) {

  1.         int mid = (left + right) / 2;
  3.         if(left > right)//左边的下标都比右边的大了，说明全部找完了也没找到
  4.             return -1;
  5.         else
  6.         {
  7.             if (array[mid] < key)//如果要找的数比array[mid]大，就说明在mid右边，向右递归
  8.                 return BinarySearch(array, key, mid + 1, right);
  9.             else if (array[mid] > key)//反之，同理
  10.                 return BinarySearch(array, key, left, mid - 1);
  11.             else//找到了array[mid]==key
  12.                 return mid;
  14.         }
  15.     }
  16. }

}

```

以上代码是查找一个值，找到就返回。 如果有多个相同的数，要查找这个是的全部下标，上面的代码小小的改进一下。返回的不是int了，而是List。在return mid那里改进。因为是有序的，相同的数字都会排在一起，所以向mid的左右判断是不是相同的，全部你加入List里面，找完了就返回这个List