Binary Search

Binary Search is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Binary Search Patterns pattern, in the On Sorted Array/List subpattern.

Problem statement

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

Constraints:

- 1 <= nums.length <= 104

- -104 < nums[i], target < 104

- All the integers in nums are unique.

- nums is sorted in ascending order.

Topics and companies

Topics: Array, Binary Search.

Reported in interviews at Microsoft, Facebook, Amazon.

How to practise Binary Search on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(logn) time and O(1) space.

Open Binary Search in the code editor, or read the Binary Search editorial for a worked solution with its approach and complexity analysis.

Where Binary Search sits in the DSA pattern sheet

• Binary Search Patterns pattern guide
• On Sorted Array/List subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Binary Search

Other problems that use the same On Sorted Array/List and Binary Search Patterns techniques:

• First Bad Version — Easy, same subpattern
• Guess Number Higher or Lower — Easy, same subpattern
• Kth Missing Positive Number — Easy, same subpattern
• Search a 2D Matrix — Medium, same subpattern
• Search Insert Position — Easy, same subpattern
• Single Element in a Sorted Array — Medium, same subpattern