6. Searching

Binary search

0 of 5 activities0%

Reading 1

Low, mid, high

Open

On a sorted array, compare the target to the middle. Discard half each time.

Iterative or recursive. O(log n) time, O(1) extra space iterative.

Careful with mid = lo + (hi-lo)/2 to avoid overflow habits, and with inclusive/exclusive bounds.

int lo=0, hi=n-1;
while(lo<=hi){
  int mid=lo+(hi-lo)/2;
  if(a[mid]==t) return mid;
  if(a[mid]<t) lo=mid+1;
  else hi=mid-1;
}

Check 2

Open

Binary search needs the array to be

Fill in 3

Open

Try it 4

Open

Sorted array.

main.cpp

Loading editor…

Program input (stdin)

Output will appear here.

Assignment 5

Open

Read n, n sorted ints ascending, then t. Print index or -1 using binary search.

main.cpp

Loading editor…