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

Question

Accepted Answer

Binary search is an efficient algorithm for finding an item from a sorted list of items.

Binary search works on sorted arrays. Example: [1, 2, 3, 4, 5].
It divides the search interval in half. If the target is less than the middle element, search the left half.
Time complexity is O(log n), making it faster than linear search (O(n)).
Example: To find 3 in [1, 2, 3, 4, 5], check middle (3), found it immediately.

Asked in TCS and 16 others

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

Interview Questions from Popular Companies