THINK FIRST·CODE LATER

← All labs

Recursive binary search and palindromes

Problem

Write RecursiveSearch with two recursive methods:

  • int binarySearch(int[] a, int key, int low, int high) — prints each range it examines, look at [0..6], middle a[3] = 23, and returns the index or −1;
  • boolean isPalindrome(String s, int low, int high) — compares the outer characters (ignore case) and recurses on the inside.

main reads n and n sorted integers, then keys to search until a non-number, then words to test until the end of input:

search 31:
  look at [0..6], middle a[3] = 23
  look at [4..6], middle a[5] = 42
  look at [4..4], middle a[4] = 31
  found at index 4
Level palindrome: true

Data for this lab

Your program reads its data from standard input. Download the file, then give it to your program as shown below. Start with data set 1: its expected output is given.

l17-3-data-1.txt

7 4 9 15 23 31 42 50 31 4 5 Level noon Java
What your program must print for l17-3-data-1.txt
search 31:
  look at [0..6], middle a[3] = 23
  look at [4..6], middle a[5] = 42
  look at [4..4], middle a[4] = 31
  found at index 4
search 4:
  look at [0..6], middle a[3] = 23
  look at [0..2], middle a[1] = 9
  look at [0..0], middle a[0] = 4
  found at index 0
search 5:
  look at [0..6], middle a[3] = 23
  look at [0..2], middle a[1] = 9
  look at [0..0], middle a[0] = 4
  not found
Level palindrome: true
noon palindrome: true
Java palindrome: false

Run your program first, then open this and compare line by line: your output must contain these lines exactly.

How to give the file to my program

Terminal (macOS, Linux, or Windows Command Prompt), after compiling:

java Main < l17-3-data-1.txt

Windows PowerShell does not understand <:

Get-Content l17-3-data-1.txt | java Main

IntelliJ IDEA: Run → Edit Configurations → Redirect input from. Or simply paste the content of the file into the console when the program waits for input.

Write it here or in your IDE, then paste it. Compile and test it yourself before comparing. Your code stays in your browser — it is never sent to or stored on the server.