###### tags: `Leetcode` `easy` `binary search` `python` `c++`

# 704. Binary Search

## [題目連結:] https://leetcode.com/problems/binary-search/description/

## 題目:
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.

**Example 1:**

Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4

**Example 2:**

Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1
Explanation: 2 does not exist in nums so return -1

## 解題想法:
* 基本的二分法 找到target回傳其位置，否則-1

## Python:

class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left=0
        right=len(nums)-1
        while left<=right:
            mid=(left+right)//2
            if nums[mid]==target:
                return mid
            elif nums[mid]>target:
                right=mid-1
            else:
                left=mid+1
        return -1

## C++:
* 萬用標題檔 #include<bits/stdc++.h>

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0, right=nums.size()-1;
        while (left<=right){
            int mid=(left+right)/2;
            if (nums[mid]==target)
                return mid;
            else if (nums[mid]>target)
                right=mid-1;
            else
                left=mid+1;
        }
        return -1;
    }
};

int main(){
    Solution res;
    vector<int> nums={-1,0,3,5,9,12};
    int target=9;
    int ans=res.search(nums,target);
    cout<<ans<<endl;
    return 0;
}