# [Leetcode 704]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

C code solution:

`int search(int* nums, int numsSize, int target){`

int idx = -1;

int left = 0;

int right = numsSize-1;

while(left <= right){

int mid = (left + right) / 2;

if(nums[mid] < target){

left = mid+1;

}else if(nums[mid] > target){

right = mid-1;

}else{

idx = mid;

break;

}

}

return idx;

}

Explanation:

每次都選擇檢查中間的那個數。一開始設定檢查一整個array，設定left為左側index，right為右側index，算出mid為中間index。檢查mid是否為target。若否且比target小，代表target可能在右側，所以將left設成mid+1。若比target大，代表target可能在左側，所以將right設成mid-1。重複找每個區段中間那個數直到不符合left≤right。時間複雜度為O(logn)。