Array Index & Element Equality

[esthicodes]

Given a sorted array arr of distinct integers, write a function indexEqualsValueSearch that returns the lowest index i for which arr[i] == i. Return -1 if there is no such index. Analyze the time and space complexities of your solution and explain its correctness.

import java.io.*;
import java.util.*;

class Solution {
  
  static int indexEqualsValueSearch(int[] arr) {
    // your code goes here: https://youtu.be/yi0wajPDc7k
    for(int i = 0; i < arr.length; i++){
      if(arr[i] == i){
        return i;
      }
    }
    
    
    
  }

  public static void main(String[] args) {

  }

}

EXAMPLES:

`input: arr = [-8,0,2,5]
output: 2 # since arr[2] == 2

input: arr = [-1,0,3,6]
output: -1 # since no index in arr satisfies arr[i] == i.`

Constraints:

[time limit] 5000ms

[input] array.integer arr

1 ≤ arr.length ≤ 100
[output] integer

[esthicodes]

`import java.io.;
import java.util.;

class Solution {

static int indexEqualsValueSearch(int[] arr) {
// your code goes here: https://youtu.be/yi0wajPDc7k
int left = 0;
int right = arr.length - 1;

while(left <= right){
  // int mid = round((left + rigth)/2);
  int mid = left + (right - left)/2;
  // i = round((start + end) / 2)
  
  if(arr[mid] == mid){
      return mid;
  }
  else if(arr[mid] < mid){
    left = mid + 1;
    
  }
  else{
    right = mid - 1;
  }
}

// for(int i = 0; i < arr.length; i++){
// if(arr[i] == i){
// return i;
// }
// }

return -1;

}

public static void main(String[] args) {

}

}`

[esthicodes]

[esthicodes]

Bildschirmaufnahme.2023-01-26.um.11.52.04.mov

Bildschirmaufnahme.2023-01-26.um.11.49.59.mov

Bildschirmaufnahme.2023-01-26.um.11.49.05.mov

[esthicodes]

`package pramp;

public class HTree {
public static void main(String[] args) {
drawHTree(0,0,8,2);
}
public static void drawLine(double x1, double y1, double x2, double y2) {
System.out.println("Line is drawn by the point: " + "(" + x1 + "," + y1 + ")" + "and" + "(" + x2 + "," + y2 + ")" );

}

public static void drawHTree(double x, double y, double length, int depth)
{
if (depth == 0 ) return;
double x0 = x - length / 2;
double x1 = x + length / 2;
double y0 = y - length / 2;
double y1 = y + length / 2;

// draw the 3 line segments of the H-Tree
drawLine(x0, y0, x0, y1); // left segment 
drawLine(x1, y0, x1, y1); // right segment 
drawLine(x0, y, x1, y); // connect segment

// at each stage, the length of segments decreases by a factor of #2
double newLength = length / Math.sqrt(2);

// decrement depth by 1 and draw an H-tree
// at each of the tips of the current 'H'
drawHTree(x0, y0, newLength, depth -1); // lower H-tree left 
drawHTree(x0, y1, newLength, depth -1); // upper left H-tree
drawHTree(x1, y0, newLength, depth -1); // lower right H-tree
drawHTree(x1, y1, newLength, depth -1); // 
}

}`