# Binary Search - 二分查找 ### Source - lintcode: [lintcode - (14) Binary Search](http://www.lintcode.com/en/problem/binary-search/) ### Problem For a given sorted array (ascending order) and a `target` number, find thefirst index of this number in `O(log n)` time complexity. If the target number does not exist in the array, return `-1`. #### Example If the array is `[1, 2, 3, 3, 4, 5, 10]`, for given target `3`, return `2`. #### Challenge If the count of numbers is bigger than 2322^{32}232, can your code work properly? ### 題解 對于已排序升序(升序)數組，使用二分查找可滿足復雜度要求，注意數組中可能有重復值，所以需要使用類似`lower_bound`中提到的方法。 ### Java ~~~ class Solution { /** * @param nums: The integer array. * @param target: Target to find. * @return: The first position of target. Position starts from 0. */ public int binarySearch(int[] nums, int target) { if (nums == null || nums.length == 0) { return -1; } int start = -1, end = nums.length; int mid; while (start + 1 < end) { // avoid overflow when (end + start) mid = start + (end - start) / 2; if (nums[mid] < target) { start = mid; } else { end = mid; } } if (end == nums.length || nums[end] != target) { return -1; } else { return end; } } } ~~~ ### 源碼分析 1. 首先對輸入做異常處理，數組為空或者長度為0。 1. 初始化 `start, end, mid`三個變量，這里`start`初始化為`-1`主要是考慮到`end`為`1`。注意mid的求值方法，可以防止兩個整型值相加時溢出。 1. **使用迭代而不是遞歸**進行二分查找，因為工程中遞歸寫法存在潛在溢出的可能。 1. while終止條件應為`start + 1 < end`而不是`start <= end`，`start == end`時可能出現死循環。**即循環終止條件是相鄰或相交元素時退出。**由于這里初始化時`start < end`，所以一定是`start + 1 == end`時退出循環。 1. 迭代終止時有兩種情況，一種是在原數組中找到了，這種情況下一定是`end`, 因為`start`的更新只在`nums[mid] < target`. 1. 最后判斷`end`和`target`的關系，先排除`end`為數組長度這種會引起越界的情況，然后再判斷和目標值是否相等。 ### 復雜度分析 時間復雜度 O(logn)O(\log n)O(logn), 空間復雜度 (1)(1)(1).對于題中的 follow up, Java 中數組不允許使用 long 型，如果使用 long 型，那么數組大小可大 17GB 之巨！！幾乎沒法用。 ### Reference - 《挑戰程序設計競賽》3.1節