704 - Binary Search

#easy
Given an array of integers nums which is sorted in ascending (遞增) order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
You must write an algorithm with O(log n) runtime complexity.

二元搜尋特徵:

1. array為有序排列
2. array中無重複元素(一旦有重複元素，使用二分查找法返回的元素下標可能不是唯一的)

#include <iostream>
#include <vector>
using namespace std;

int binary_search_algo(vector<int> sort_nums, int search_num) {
  int left = 0;
  int right = sort_nums.size() - 1;
  while ( left <= right )  {
    int middle = ( right + left ) / 2;
    if ( sort_nums[middle] == search_num ) {
      return middle;
    }
    else if ( sort_nums[middle] < search_num ) {
      left = middle + 1;
    }
    else {
      right = middle - 1;
    }
  }

  return -1;
} 

int main() {
  vector<int> sort_nums{1,2,3,4,5,6,7,8,9,10};
  int pos = binary_search_algo(sort_nums, 6);
  cout << pos << endl;
}