# Binary search: Find an element in an array

[Question]: 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```
##### #Approach: Dividing array into two half and search target element

We start dividing element into two half and & create a mid element until we match mid == target element
Here i have explained with two approach Iterative & recursive.

``````// Question: Binary search find array elements
// TC: O(logN), where N = size of the given array.
// SC O(1)If a number n can be divided by 2 for x times:
//2^x = n // Because we are dividing array by 2 every time.
//Therefore, x = logn (base is 2)
// Approach #1 Iterative approach.
func findElementUsingBinarySearch(nums: [Int], target: Int) -> Int {
let n = nums.count // size of the array
var low = 0
var high = n - 1
// Divide the array until we got mid element as target element.
while low <= high {
let mid = (low + high) / 2
if nums[mid] == target {
return mid
} else if target > nums[mid] {// If target is greater increase low pointer
low = mid + 1
} else {// If target is lesser decrease high pointer
high = mid - 1
}
}
return -1
}
// Approach #2 Recursion approach.
func findElementUsingBinarySearchUsingRecursion(nums: [Int], target: Int, low: inout Int, high: inout Int) -> Int {
if low > high { return -1 }// Base case.
var mid = (low + high) / 2
if nums[mid] == target {
return mid
} else if target > nums[mid] {// If target is greater increase low pointer
low = mid + 1
} else {// If target is lesser decrease high pointer
high = mid - 1
}
// Divide the array until we got mid element as target element.
return findElementUsingBinarySearchUsingRecursion(nums: nums, target: target, low: &low, high: &high)
}

let binaryArrayInput = [3, 4, 6, 7, 9, 12, 16, 17]
let targetElementToFind = 6
let binaryIndexOutput = findElementUsingBinarySearch(nums: binaryArrayInput, target: targetElementToFind)
print("binaryIndexOutput ", binaryIndexOutput)// Output 2

// Using Recursion. ---
var high = binaryArrayInput.count - 1
var low = 0
let binaryIndexOutputRecursion = findElementUsingBinarySearchUsingRecursion(nums: binaryArrayInput, target: targetElementToFind, low: &low, high: &high)
print("findElementUsingBinarySearchUsingRecursion ", binaryIndexOutputRecursion) // Output 2``````