Binary Search

Try to solve the Binary Search problem.

We'll cover the following

Statement#

We are given an array of integers, nums, sorted in ascending order, and an integer value, target. If the target exists in the array, return its index. If the target does not exist, return -1.

Constraints:

  • 11≤\leq nums.length ≤\leq 10310^3

  • −104-10^4≤\leq nums[i] , target ≤\leq 10410^4

  • All integers in nums are unique.

  • nums is sorted in ascending order.

Example#

Created with Fabric.js 3.6.6 nums -5 0 2 6 12 target 6 index 3 Sample Example 1 Input ---------------------------------------------------- Output

1 of 3

Created with Fabric.js 3.6.6 nums 100 223 467 800 999 target 223 index 1 Sample Example 2 Input Output ----------------------------------------------------

2 of 3

Created with Fabric.js 3.6.6 nums -5 10 19 35 210 target 2 index -1 ---------------------------------------------------- Input Sample Example 3 Output

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Binary Search

1

Find the index of the number 60 from the following array using binary search.

array = [-10, 11, 60, 70]

Also, calculate the number of comparisons required to find the number.

A)

index: 0, steps: 2

B)

index: 1, steps: 1

C)

index: 2, steps: 2

D)

index: 2, steps: 3

Question 1 of 40 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Find the middle element in the sorted array.

Compare the middle element with the target element. If it matches, return the index of the element.

If the target element is smaller than the middle element, perform the search on the left half of the array. Otherwise, perform the search on the right half of the array.

Repeat the process until the target value is found. Otherwise, return -1 if not found.

Try it yourself#

Implement your solution in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
%0 node_01 1 node_11 6 node_21 8 node_31 10
Visualization for Input #1
Binary Search

Solution: Search in Rotated Sorted Array

Solution: Binary Search