首页 > 代码库 > Summary: Binary Search

Summary: Binary Search

Iterative ways: 

 1 int binarySearch (int[] a, int x) { 2    int low = 0; 3    int high = a.length - 1; 4    int mid; 5  6    while (low <= high) { 7       mid = (low + high) / 2; 8       if (a[mid] < x) { 9          low = mid + 1;10       }   11       else if (a[mid] > x) {12          high = mid - 1;13       }14       else {15          return mid;16       } 17    }              18    return -1;19 }

Recursive ways:

 1 int binarySearchRecursive (int[] a, int x, int low, int high) { 2     if (low > high) return -1; //error 3      4     int mid = (low + high) / 2; 5     if (a[mid] < x) { 6         return binarySearchRecursive(a, x, mid + 1, high); 7     } 8     else if (a[mid] > x) { 9         return binarySearchRecursive(a, x, low, mid - 1);10     }11     else {12         return mid;13     }14 }