When we think of searching algorithms, we generally think of binary search.

算法general實現(xiàn)方式：

Java Version:

// nums is a sorted and valid array.
public int findTargetIndex(int[] nums, int target) {
  int start = 0;
  int end = nums.length - 1;
  int mid;

  while(start <= end) {
    mid = start + (end - start) / 2;
    if (nums[mid] == target) {
      return mid;
    } else if (nums[mid] < target) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }

  return -1;
}

Ruby Version:

def find_target_index(nums, target)
  low = 0;
  high = nums.length - 1

  while (low <= high)
    mid = low + (high - low) / 2
    return mid if nums.at(mid) == target
    if nums.at(mid) < target
      low = mid + 1
    else
      high = mid - 1
    end
  end

  return -1
end

Summary:

1. mid 的更新方式 mid = start + (end - start) / 2 為偏向start方向的移動，當 end == start + 1 時，mid 的值為 start
2. 循環(huán)判斷條件為 start <= end，包含了 nums.length == 1的情況
3. start 的更新方式應為 mid + 1，否則下面的例子會出現(xiàn)死循環(huán)的：
   • mid 取中后等于 start，且 nums[mid] < target
   • target 大于 nums 中所有值（實際上，該Case最終iteration會是上面的Case）
4. end 的更新方式為 mid - 1，否則下例會出現(xiàn)死循環(huán)：target 小于 nums 中的所有值。
5. 如果nums中不存在 target，那么while循環(huán)的最終結果為 start == end + 1，排序角度來講，該 target 在nums 中應該放置于 end 和 start 之間。

論證：

Case 1: start == end - 1, 那么新的 mid 值為 start:
if nums[mid] < target, start 更新為 mid + 1, 即為 end，歸納為Case 2
if nums[mid] > target, end 更新為 mid - 1，即為 start - 1，循環(huán)結束

Case 2: start == end，那么新的 mid 值為 start:
if nums[mid] < target, start 更新為 mid + 1，即為 end + 1，循環(huán)結束
if nums[mid] > target, end 更新為 mid - 1，即為 start - 1，循環(huán)結束

Case 1 & 2 循環(huán)最終結果為 start == end + 1

6. target 超出 nums 范圍的情況:
   6.1 nums 中所有items 大于 target，結果：start 值為
   nums.length, end 值為 nums.length - 1.
   6.2 nums 中所有 items 大于 target，結果：start 值為 0， end 值為 -1.

延伸

Binary Search 的思想延伸及優(yōu)化可能性：

• search a node in Binary Search Tree
• Hash Map

Heap 是 Binary Search Tree 的延伸，Heap是使用array實現(xiàn)的 balanced BST。